Форум на Исходниках.RU

Оптимальный алгоритм максимизации для игры

shm — Tue, 28 Mar 2023 19:06:10 +0000

shm:

Цитата Profi @ 28.03.23, 19:04

задача сводится к определению что сейчас делать И1, брать число или пропускать и брать ли два подряд и когда.

Фактически так и есть.

Оптимальный алгоритм максимизации для игры

Profi — Tue, 28 Mar 2023 19:04:50 +0000

Profi: Какая-то неполная задача.
Если во входном массиве нельзя менять порядок, то задача сводится к определению что сейчас делать И1, брать число или пропускать и брать ли два подряд и когда.
Если можно - то задача сводится к нахождению максимальной суммы и расстановки чисел в нужном порядке.
Короче - я бы потребовал уточнения ТЗ. :)

Оптимальный алгоритм максимизации для игры

shm — Tue, 28 Mar 2023 16:43:30 +0000

shm:

Цитата Akina @ 28.03.23, 16:10

один за другим, или строго первое из оставшихся в списке?

не понял вопроса. Можно взять только самое первое число. Но И1 может не брать вообще числе или 1 раз за игру взять 2 (крайних) числа.

Цитата Akina @ 28.03.23, 16:10

1 - это "одно число" или "первое число из оставшихся в списке"?

первое в оставшемся списке

Добавлено 28.03.23, 16:45
Почитал про динамическое программирование (мне тут посоветовали) - голова опухла, много всяких умных формул, а я не математик. А что в универе было уже забыл за много лет:)
Короче я сам дошел до решения за O(N). Вернулся к исследованию переборочного варианта (сперва я ушел не в ту сторону на метод ветвей и границ), заметил, что много повторных вычислений в узлах дерева. Решил переделать на поиск в глубину, это позволило дать возможность закэшировать результаты вычислений. Потом в процессе отладки до меня дошло, что по факту тут хвостовая рекурсия, которую можно развернуть:

n = int(input(''))

v = [int(x) for x in input('').split()]

r1 = [0] * (n + 3)

r2 = [0] * (n + 3)

r1[n - 1] = v[n - 1]

r2[n - 1] = v[n - 1]

for i in reversed(range(0, n - 1)):

r1[i] = max(v[i] + r1[i + 2], r1[i + 1], v[i] + v[i + 1] + r2[i + 3])

r2[i] = max(v[i] + r2[i + 2], r2[i + 1])

print(r1[0])

Проходит все тесты макс. за 70мс при допустимой 1 сек. С этой задачей мне попросил помочь знакомый студент. Лично мое мнение - препод издевается.

Оптимальный алгоритм максимизации для игры

Akina — Tue, 28 Mar 2023 16:10:25 +0000

Akina: Вот вроде элементарно всё... но чем дальше читаешь пояснения, тем больше убеждаешься, что на самом деле поставленная задача очень слабо связана с тем, что написано в вопросе. Слова вроде правильные, но вот расставлены они чёрт те как...

Цитата shm @ 28.03.23, 11:50

два игрока И1 и И2, которые последовательно берут по числу

Последовательно - это как? один за другим, или строго первое из оставшихся в списке?

Цитата shm @ 28.03.23, 11:50

И2 играет всегда "глупо" - берет 1 число на своем на своем ходу.

1 - это "одно число" или "первое число из оставшихся в списке"?

Оптимальный алгоритм максимизации для игры

shm — Tue, 28 Mar 2023 12:38:07 +0000

shm:

Цитата FasterHarder @ 28.03.23, 12:31

81 71 69 63 54 35 28 12 5

= 262 < 320

Цитата FasterHarder @ 28.03.23, 12:31

вот сумма для И1, если И2 будет макс. мешать...

:wall:

Оптимальный алгоритм максимизации для игры

FasterHarder — Tue, 28 Mar 2023 12:31:32 +0000

FasterHarder: A= [69 81 71 18 35 28 12 63 5 54]
81 71 69 63 54 35 28 12 5

вот сумма для И1, если И2 будет макс. мешать...

Добавлено 28.03.23, 12:34
почему это слева И2 должен брать - перед ним список всех чисел
И1 отдавать слева числа, а для и2 - справа ( там минимумы )

короче все

Оптимальный алгоритм максимизации для игры

shm — Tue, 28 Mar 2023 12:29:34 +0000

shm:

Цитата FasterHarder @ 28.03.23, 12:28

кто тебе сказал, что И2 отдаст число 63)
вообще понятие "глупый ход" как бы не формализован

И2 всегда забирает крайнее левое число на своем ходу. Куда ж формальнее?

Добавлено 28.03.23, 12:30

Цитата FasterHarder @ 28.03.23, 12:28

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

Тут такие условия. Свои условия придумывать не надо.

Оптимальный алгоритм максимизации для игры

FasterHarder — Tue, 28 Mar 2023 12:28:29 +0000

FasterHarder:

Цитата shm @ 28.03.23, 12:20

Приложи, плз, полный результат, который удовлетворяет условию и дает 320 в сумме.

кто тебе сказал, что И2 отдаст число 63)
вообще понятие "глупый ход" как бы не формализован

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

если И2 берет число НА РАНДОМЕ, то макс. сумма для И1 будет меняться...

Оптимальный алгоритм максимизации для игры

shm — Tue, 28 Mar 2023 12:20:37 +0000

shm:

Цитата FasterHarder @ 28.03.23, 12:17

опровергни

Приложи, плз, полный результат, который удовлетворяет условию и дает 320 в сумме.

Цитата FasterHarder @ 28.03.23, 12:17

зы: или сортировать НЕЛЬЗЯ и числа поступают ПО ОДНОМУ и сразу подвергаются обработке, то тогда, да, по-другому нужно

Сортировать можно, весь список чисел известен заранее.

Оптимальный алгоритм максимизации для игры

FasterHarder — Tue, 28 Mar 2023 12:17:02 +0000

FasterHarder: A= [69 81 71 18 35 28 12 63 5 54]

after sort

A = [ 81, 71, 69, 63, ... ]
И1 = 81 + 71 - first move
И2 = 69 - first move

опровергни

зы: или сортировать НЕЛЬЗЯ и числа поступают ПО ОДНОМУ и сразу подвергаются обработке, то тогда, да, по-другому нужно

Оптимальный алгоритм максимизации для игры

shm — Tue, 28 Mar 2023 12:11:59 +0000

shm:

Цитата FasterHarder @ 28.03.23, 12:07

И1 1ым ходом ВСЕГДА берет сходу 2 числа ( они макс. для всей посл. )

Идея уже терпит неудачу для моего примера. Максимальные числа - 71 и 81, но если взять 71, то максимального результата не достичь.

Добавлено 28.03.23, 12:13
Более того, порядок чисел в этой игре важен. Если отсортировать массив, то будет другой результат на переборном алгоритме.

Добавлено 28.03.23, 12:13

Цитата FasterHarder @ 28.03.23, 12:07

2 идея: max - heap

А можно более подробно?

Оптимальный алгоритм максимизации для игры

FasterHarder — Tue, 28 Mar 2023 12:07:11 +0000

FasterHarder: отсортировать по убыванию ( наибыстрейшей сортировкой )
И1 1ым ходом ВСЕГДА берет сходу 2 числа ( они макс. для всей посл. )
пропускать ход ведь смысла вроде нет ( если отр. чисел нет )
И затем И1 и И2 последовательно берут по порядку числа
-------------------
2 идея: max - heap

это так, навскидку, может и не проканает ничего из этого...

Оптимальный алгоритм максимизации для игры

shm — Tue, 28 Mar 2023 11:50:59 +0000

shm: Игра довольно простая. Есть последовательность чисел A длины N, есть два игрока И1 и И2, которые последовательно берут по числу. Игроки ходят поочередно, но И1 начинает игру всегда первым. Смысл игры - набрать максимальную сумму чисел. И1 на своем ходу может взять 1 число или пропустить ход. Также один раз за всю игру И1 может взять 2 числа. И2 играет всегда "глупо" - берет 1 число на своем на своем ходу. Смысл задачи - просчитать максимально возможный выигрыш для И1.
Пример:
A= [69 81 71 18 35 28 12 63 5 54]
Жирным выделены числа, которые забрал И1. Результат - 320.
Ограничения N <= 10⁵, 0 <= A_i <= 100

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