Максимизируйте разницу суммы выбранных номеров 2 игроками - PullRequest
Новая
       37

Максимизируйте разницу суммы выбранных номеров 2 игроками

0 голосов
/ 03 апреля 2019

У меня есть 2 проблемы, которые вытекают из простой проблемы. Я объясню простой с решением, которое я нашел, и после этого измененную проблему.

Предположим, что есть игра с 2 игроками, А и В, и список целые положительные числа. Игрок А начинает с того, что вынимает число из списка, игрок B делает то же самое и так далее, после того, как больше нет чисел в список. Оба игрока суммируют выбранные цифры. Цель для каждого игрока, чтобы максимизировать разницу между его суммой и сумма противника, которая является счетом. Вопрос в том, что является максимальное количество очков игрок может получить, если оба игрока играют в оптимальном образом.

Теперь для этого я выяснил, что оптимальная стратегия для каждого игрока - брать наибольшее число на каждом шаге, псевдокод следующий: 

sumA = 0
sumB = 0
list = [1, 5, 3, 7, 9]

while list IS NOT EMPTY:
    val = pop_max(list)
    sumA = sumA + val

    if list IS NOT EMPTY:
        val = pop_max(list)
        sumB = sumB + val


scoreA = sumA - sumB
print scoreA

Это может выполняться в O (n) или O (n * log (n)) в зависимости от того, как отсортированы числа из списка.

Следующие 2 модификации:

В начале игры игрок A должен удалить K чисел из списка. Если он делает это оптимальным образом и после этого игры являются начальными, какую максимальную оценку он может получить?

и

На каждом шаге игроки могут выбрать самый левый или самый правый номер из списка. Снова они играют оптимальным образом. Какой максимальный балл может получить игрок А?

Для второй модификации я могу придумать подход грубой силы, то есть вычисление дерева всех возможностей, но это не работает для больших входных данных. Я считаю, что есть какой-то алгоритм DP.

Для первой модификации я не могу придумать идею.

Может кто-нибудь помочь с некоторыми идеями алгоритма для 2 модификаций?

[LATTER EDIT]

Решение для 2-й модификации можно найти здесь https://www.geeksforgeeks.org/optimal-strategy-for-a-game-dp-31/ Это DP.

1 Ответ

0 голосов
/ 06 апреля 2019

Вот пост для 2-й модификации, которая

На каждом шаге игроки могут выбрать самый левый или самый правый номер из списка. Снова они играют оптимальным образом. Какой максимальный балл может получить игрок А?

Решение основано на DP. Для подзадачи (i-j), т. Е. v[]i, v[i+1], ..., v[j], есть два варианта:

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

enter image description here

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

enter image description here

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

F (i, j) представляет собой максимальное значение, которое пользователь может получить от i-й монеты до j-й монеты.

F (i, j) = Макс (v [i] + min (F (i + 2, j), F (i + 1, j-1)), v [j] + min (F (i +1, j-1), F (i, j-2)))

Базовые чехлы

F (i, j) = v [i] Если j == i

F (i, j) = max (v [i], v [j]), если j == i + 1

Вот кусок кода на Python, который решает его 

def optimalStrategyOfGame(arr, n): 

    # Create a table to store solutions of subproblems  
    table = [[0 for i in range(n)] for i in range(n)] 

    # Fill table using above recursive formula. Note that the table is  
    # filled in diagonal fashion from diagonal elements to table[0][n-1] which is the result.  
    for gap in range(n): 
        for j in range(gap, n): 
            i = j - gap 

            # Here x is value of F(i+2, j), y is F(i+1, j-1) and z is  
            # F(i, j-2) in above recursive formula  
            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]

[ИСТОЧНИК] https://www.geeksforgeeks.org/optimal-strategy-for-a-game-dp-31/

...