Рубрики

Оптимальная стратегия для игры | DP-31

Постановка задачи: рассмотрим ряд из n монет значений v1. , , vn, где n четное. Мы играем в игру против оппонента, чередуя ходы. В каждом ходу игрок выбирает первую или последнюю монету из ряда, навсегда удаляет ее из ряда и получает ценность монеты. Определите максимально возможную сумму денег, которую мы можем определенно выиграть, если будем двигаться первым.

Примечание: противник такой же умный, как и пользователь.

Позвольте нам понять проблему с несколькими примерами:

1. 5, 3, 7, 10: пользователь получает максимальное значение как 15 (10 + 5)

2. 8, 15, 3, 7: пользователь получает максимальное значение как 22 (7 + 15)

Дает ли выбор лучшего при каждом движении оптимальное решение?

Нет. Во втором примере игра может закончиться так:

1.
……. Пользователь выбирает 8.
……. Противник выбирает 15.
……. Пользователь выбирает 7.
……. Оппонент выбирает 3.
Общая стоимость, собранная пользователем составляет 15 (8 + 7)
2.
……. Пользователь выбирает 7.
……. Оппонент выбирает 8.
……. Пользователь выбирает 15.
……. Оппонент выбирает 3.
Общая стоимость, собранная пользователем 22 (7 + 15)
Таким образом, если пользователь следует за вторым игровым состоянием, максимальное значение может быть получено, хотя первый ход не самый лучший.

Есть два варианта:
1. Пользователь выбирает i-ю монету со значением Vi: оппонент выбирает (i + 1) -ю или j-ю монету. Оппонент намеревается выбрать монету, которая оставляет пользователю минимальное значение.
т.е. пользователь может собрать значение Vi + min (F (i + 2, j), F (i + 1, j-1))

2. Пользователь выбирает j-ю монету со значением Vj: оппонент выбирает i-ю монету или (j-1) -ю монету. Оппонент намеревается выбрать монету, которая оставляет пользователю минимальное значение.
т.е. пользователь может собрать значение Vj + min (F (i + 1, j-1), F (i, j-2))

Ниже приводится рекурсивное решение, основанное на двух вышеупомянутых вариантах. Мы берем максимум два варианта.

F(i, j)  represents the maximum value the user can collect from 
         i'th coin to j'th coin.

    F(i, j)  = Max(Vi + min(F(i+2, j), F(i+1, j-1) ), 
                   Vj + min(F(i+1, j-1), F(i, j-2) )) 
Base Cases
    F(i, j)  = Vi           If j == i
    F(i, j)  = max(Vi, Vj)  If j == i+1

Почему динамическое программирование?
Вышеупомянутое соотношение имеет перекрывающиеся подзадачи. В приведенном выше соотношении F (i + 1, j-1) рассчитывается дважды.

C ++

// C ++ программа для определения максимального значения из
// заданная последовательность монет
#include <bits/stdc++.h>

using namespace std;

  
// Возвращает оптимальное возможное значение, которое игрок может
// собирать из массива монет размером n. Заметка
// чем n должно быть четным

int optimalStrategyOfGame(int* arr, int n)

{

    // Создать таблицу для хранения решений подзадач

    int table[n][n];

  

    // Заполнить таблицу, используя приведенную выше рекурсивную формулу. Заметка

    // таблица заполнена по диагонали (аналогично

    // to http://goo.gl/PQqoS ), от диагональных элементов до

    // таблица [0] [n-1], которая является результатом.

    for (int gap = 0; gap < n; ++gap) {

        for (int i = 0, j = gap; j < n; ++i, ++j) {

  

            // Здесь x - это значение F (i + 2, j), y - это F (i + 1, j-1) и

            // z - это F (i, j-2) в приведенной выше рекурсивной формуле

            int x = ((i + 2) <= j) ? table[i + 2][j] : 0;

            int y = ((i + 1) <= (j - 1)) ? table[i + 1][j - 1] : 0;

            int z = (i <= (j - 2)) ? table[i][j - 2] : 0;

  

            table[i][j] = max(arr[i] + min(x, y), arr[j] + min(y, z));

        }

    }

  

    return table[0][n - 1];

}

  
// Программа драйвера для проверки вышеуказанной функции

int main()

{

    int arr1[] = { 8, 15, 3, 7 };

    int n = sizeof(arr1) / sizeof(arr1[0]);

    printf("%d\n", optimalStrategyOfGame(arr1, n));

  

    int arr2[] = { 2, 2, 2, 2 };

    n = sizeof(arr2) / sizeof(arr2[0]);

    printf("%d\n", optimalStrategyOfGame(arr2, n));

  

    int arr3[] = { 20, 30, 2, 2, 2, 10 };

    n = sizeof(arr3) / sizeof(arr3[0]);

    printf("%d\n", optimalStrategyOfGame(arr3, n));

  

    return 0;

}

Джава

// Java программа, чтобы узнать максимум
// значение из заданной последовательности монет

import java.io.*;

  

class GFG {

  

    // Возвращает оптимальное значение, которое возможно игроку

    // можем собрать из массива монет размером n.

    // Обратите внимание, что n должно быть четным

    static int optimalStrategyOfGame(int arr[], int n)

    {

        // Создать таблицу для хранения решений подзадач

        int table[][] = new int[n][n];

        int gap, i, j, x, y, z;

  

        // Заполнить таблицу, используя приведенную выше рекурсивную формулу.

        // Обратите внимание, что таблица заполнена по диагонали

        // мода (аналог http://goo.gl/PQqoS ),

        // из диагональных элементов в таблицу [0] [n-1]

        // что является результатом.

        for (gap = 0; gap < n; ++gap) {

            for (i = 0, j = gap; j < n; ++i, ++j) {

  

                // Здесь x - это значение F (i + 2, j),

                // у есть F (i + 1, j-1) и z

                // F (i, j-2) в приведенной выше рекурсивной формуле

                x = ((i + 2) <= j) ? table[i + 2][j] : 0;

                y = ((i + 1) <= (j - 1)) ? table[i + 1][j - 1] : 0;

                z = (i <= (j - 2)) ? table[i][j - 2] : 0;

  

                table[i][j] = Math.max(arr[i] + Math.min(x, y), 

                                       arr[j] + Math.min(y, z));

            }

        }

  

        return table[0][n - 1];

    }

  

    // Драйвер программы

    public static void main(String[] args)

    {

        int arr1[] = { 8, 15, 3, 7 };

        int n = arr1.length;

        System.out.println("" + optimalStrategyOfGame(arr1, n));

  

        int arr2[] = { 2, 2, 2, 2 };

        n = arr2.length;

        System.out.println("" + optimalStrategyOfGame(arr2, n));

  

        int arr3[] = { 20, 30, 2, 2, 2, 10 };

        n = arr3.length;

        System.out.println("" + optimalStrategyOfGame(arr3, n));

    }

}

  
// Этот код предоставлен vt_m

python3

# Python3 программа, чтобы узнать максимум
# значение из заданной последовательности монет

  
# Возвращает оптимальное значение, которое возможно
# игрок может собрать из массива
количество монет размером n. Обратите внимание, чем п
# должно быть четным

def optimalStrategyOfGame(arr, n):

      

    # Создать таблицу для хранения

    # решения подзадач

    table = [[0 for i in range(n)]

                for i in range(n)]

  

    # Заполнить таблицу с использованием выше рекурсивного

    # формула. Обратите внимание, что таблица

    # заполнены по диагонали

    # (похоже на http://goo.gl/PQqoS ),

    # от диагональных элементов до

    # table [0] [n-1], который является результатом.

    for gap in range(n):

        for j in range(gap, n):

            i = j - gap

              

            # Здесь x - это значение F (i + 2, j),

            # у есть F (i + 1, j-1) и z

            # F (i, j-2) выше рекурсивно

            # формула

            x = 0

            if((i + 2) <= j):

                x = table[i + 2][j]

            y = 0

            if((i + 1) <= (j - 1)):

                y = table[i + 1][j - 1]

            z = 0

            if(i <= (j - 2)):

                z = table[i][j - 2]

            table[i][j] = max(arr[i] + min(x, y),

                              arr[j] + min(y, z))

    return table[0][n - 1]

  
Код водителя

arr1 = [ 8, 15, 3, 7 ]

n = len(arr1)

print(optimalStrategyOfGame(arr1, n))

  

arr2 = [ 2, 2, 2, 2 ]

n = len(arr2)

print(optimalStrategyOfGame(arr2, n))

  

arr3 = [ 20, 30, 2, 2, 2, 10]

n = len(arr3)

print(optimalStrategyOfGame(arr3, n))

  
# Этот код продолжается
# от sahilshelangia

C #

// C # программа, чтобы узнать максимум
// значение из заданной последовательности монет

using System;

  

public class GFG{

      

      

    // Возвращает оптимальное значение, которое возможно игроку

    // можем собрать из массива монет размером n.

    // Обратите внимание, что n должно быть четным

    static int optimalStrategyOfGame(int []arr, int n) 

    

        // Создать таблицу для хранения решений подзадач

        int [,]table = new int[n,n]; 

        int gap, i, j, x, y, z; 

  

        // Заполнить таблицу, используя приведенную выше рекурсивную формулу.

        // Обратите внимание, что таблица заполнена по диагонали

        // мода (аналог http://goo.gl/PQqoS ),

        // из диагональных элементов в таблицу [0] [n-1]

        // что является результатом.

        for (gap = 0; gap < n; ++gap) { 

            for (i = 0, j = gap; j < n; ++i, ++j) { 

  

                // Здесь x - это значение F (i + 2, j),

                // у есть F (i + 1, j-1) и z

                // F (i, j-2) в приведенной выше рекурсивной формуле

                x = ((i + 2) <= j) ? table[i + 2,j] : 0; 

                y = ((i + 1) <= (j - 1)) ? table[i + 1,j - 1] : 0; 

                z = (i <= (j - 2)) ? table[i,j - 2] : 0; 

  

                table[i,j] = Math.Max(arr[i] + Math.Min(x, y), 

                                    arr[j] + Math.Min(y, z)); 

            

        

  

        return table[0,n - 1]; 

    

  

    // Драйвер программы

      

    static public void Main (){

        int []arr1 = { 8, 15, 3, 7 }; 

        int n = arr1.Length; 

        Console.WriteLine("" + optimalStrategyOfGame(arr1, n)); 

  

        int []arr2 = { 2, 2, 2, 2 }; 

        n = arr2.Length; 

        Console.WriteLine("" + optimalStrategyOfGame(arr2, n)); 

  

        int []arr3 = { 20, 30, 2, 2, 2, 10 }; 

        n = arr3.Length; 

        Console.WriteLine("" + optimalStrategyOfGame(arr3, n)); 

    

  
// Этот код предоставлен ajit

PHP

<?php
// PHP программа для определения максимального значения
// из заданной последовательности монет

  
// Возвращает оптимальное значение, которое возможно
// игрок может собрать из массива
// монеты размером n. Обратите внимание, что n должно быть четным

function optimalStrategyOfGame($arr, $n)

{

    // Создать таблицу для хранения решений

    // подзадач

    $table = array_fill(0, $n

             array_fill(0, $n, 0));

  

    // Заполнить таблицу, используя приведенную выше рекурсивную формулу.

    // Обратите внимание, что таблица заполнена по диагонали

    // мода (аналог http://goo.gl/PQqoS ),

    // из диагональных элементов в таблицу [0] [n-1]

    // что является результатом.

    for ($gap = 0; $gap < $n; ++$gap)

    {

        for ($i = 0, $j = $gap; $j < $n; ++$i, ++$j

        {

  

            // Здесь x - это значение F (i + 2, j),

            // у есть F (i + 1, j-1) и z это F (i, j-2)

            // в приведенной выше рекурсивной формуле

            $x = (($i + 2) <= $j) ? 

               $table[$i + 2][$j] : 0;

            $y = (($i + 1) <= ($j - 1)) ? 

                 $table[$i + 1][$j - 1] : 0;

            $z = ($i <= ($j - 2)) ? 

               $table[$i][$j - 2] : 0;

  

            $table[$i][$j] = max($arr[$i] + min($x, $y), 

                                 $arr[$j] + min($y, $z));

        }

    }

  

    return $table[0][$n - 1];

}

  
// Код драйвера

$arr1 = array( 8, 15, 3, 7 );

$n = count($arr1);

print(optimalStrategyOfGame($arr1, $n) . "\n");

  

$arr2 = array( 2, 2, 2, 2 );

$n = count($arr2);

print(optimalStrategyOfGame($arr2, $n) . "\n");

  

$arr3 = array(20, 30, 2, 2, 2, 10);

$n = count($arr3);

print(optimalStrategyOfGame($arr3, $n) . "\n");

  
// Этот код предоставлен chandan_jnu
?>


Выход:

22
4
42

Приведенное выше решение можно оптимизировать, используя меньшее количество сравнений для каждого выбора. Пожалуйста, обратитесь ниже.
Оптимальная стратегия для игры | Набор 2

Упражнение
Ваши мысли о стратегии, когда пользователь желает выиграть только вместо того, чтобы выиграть с максимальной ценностью. Как и над проблемой, количество монет чётно.
Может ли жадный подход работать достаточно хорошо и дать оптимальное решение? Изменится ли ваш ответ, если количество монет нечетное? Пожалуйста, смотрите монета игра двух углов

Эта статья составлена Aashish Barnwal . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Оптимальная стратегия для игры | DP-31

0.00 (0%) 0 votes