Игра выбора максимальной суммы после оптимального удаления K монет

Question

Мне дано решение следующей задачи:
В игру играют два игрока.В этой игре есть монеты, и каждая монета имеет значение.Каждый игрок по очереди выбирает 1 монету.Цель состоит в том, чтобы иметь наибольшую общую стоимость в конце.Каждый игрок вынужден играть по желанию (это означает, что он всегда выбирает наибольшее значение из колоды).Я должен выяснить сумму двух игроков / разницу между их максимально возможными суммами

Ограничения: Все значения натуральные и положительные.

Вышеприведенная задача - классическая жадная задача.Из того, что я пробовал, можно отсортировать с помощью quickSort, а затем просто выбрать элементы для двух игроков.Если вам нужно больше времени на моих тестах, Radix-Sort работает лучше.Итак, эта задача довольно проста.

Теперь у меня та же задача, что и выше, НО первый игрок должен удалить ОПТИМАЛЬНО K монет, чтобы разница между их счетами была максимальной.Ну, это звучит как DP, но мой разум не может найти решение.Я должен снова выяснить максимальную разницу между их очками (при этом оба игрока играют оптимально).Или очки двух игроков таким образом, что разница между ними максимальна.

Есть ли такой алгоритм уже реализован?Или кто-то может дать мне несколько советов по этому вопросу?

Answer 1

Вот решение для подхода DP. Мы рассматриваем n монеты, отсортированные по убыванию, чтобы упростить обозначение (значение coins[0] - монета с самым высоким значением, а coins[n-1] имеет самое низкое значение), и мы хотим удалить k монеты, чтобы выиграть игра с максимально большим запасом.
Рассмотрим матрицу M, размеры n-k на k.
M хранит следующее: M(i, j) - лучший результат после игры i ходов, когда из 1011 * лучших монет были удалены j монеты. Поначалу это может показаться немного нелогичным, но на самом деле это то, что мы ищем.
Действительно, у нас уже есть значение для инициализации нашей матрицы: M(0, 0) = 0.
Мы также видим, что M(n-k, k) на самом деле является решением проблемы, которую мы хотим решить.
Теперь нам нужны рекуррентные уравнения, чтобы заполнить нашу матрицу. Мы считаем, что хотим максимально увеличить разницу в счете для первого игрока. Чтобы максимизировать разницу очков для второго игрока, подход такой же, просто измените некоторые знаки.

if i = 0 then:
    M(i, j) = 0  // score difference is always 0 after playing 0 turns
else if j = 0 and i % 2 = 0:  // player 1 plays
    M(i, j) = M(i-1, j) + coins[i+j]
else if j = 0 and i % 2 = 1:  // player 2 plays
    M(i, j) = M(i-1, j) - coins[i+j]
else if i % 2 = 0:
    M(i, j) = max(M(i, j-1), M(i-1, j) + coins[i+j])
else if i % 2 = 1:
    M(i, j) = max(M(i, j-1), M(i-1, j) - coins[i+j])

Это повторение просто означает, что лучшим выбором в любой момент является удаление монеты (в случае, когда наилучшее значение равно M(i, j-1)) или ее удаление (случай, когда наилучшее значение равно M(i-1, j) +/- coins[i+j]). .
Это даст вам окончательную разницу очков, но не набор монет для удаления. Чтобы найти его, вы должны сохранить «оптимальный путь», который использовала ваша программа для вычисления значений матрицы (было ли наилучшее значение, полученное из M (i-1, j) или из M (i, j-1)?).
Этот путь может дать вам набор, который вы ищете. Кстати, вы можете видеть, что это имеет смысл, поскольку есть k among n возможных способов удаления k монет из n монет, а также есть k among n путей от верхнего левого до нижнего правого в k на n-k матрицу, если вам разрешено идти только вправо или вниз.
Это объяснение может все еще быть неясным, не стесняйтесь спрашивать точность в комментарии, я отредактирую ответ для большей ясности.