Блог пользователя tamir

Автор tamir, 11 лет назад, По-русски

Здравствуйте! Помогите решить задачу на ДП. Какая должна быть динамика,переходы?

Спасибо за внимание!

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

У меня есть такая идея: пусть у нас 8 гирек, тогда можно перебрать все маски вида: 00000000, 00000001 и т.д. То что нули это гирьки, которыми мы хотим решить задачу для первых двух кучек(т.е проверяем можем ли набрать этими гирями две кучки с одинаковым весом(просто перебор бит масок, если да, то запомнить все варианты с различными весами). Всё что 1 это гирьки, которыми набираем две последние кучки. Решаем как и для первых двух, затем смотрим, есть ли совпадения по весам. Сдавать не пробовал, так что в правильности не уверен.

»
11 лет назад, # |
Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

в классическом решении такой задачи общая схема динамики такая:

dp[i][j][k],

можно ли набрать i в первой кучке, j — во второй, k — в третьей. размерность динамики = количество куч — 1. (в последней всегда столько, сколько остаётся).

для данной задачи вам понадобится ~ 10^8 памяти. не очень хорошо.

Если вы заглянете в вопросы, то увидите, что автор предполагал перебор.

ну и переходы, наверное, так. берете последовательно все гирьки. для каждой перебираете все состояния вашей динамики. допустим, вес текущей = r. тогда если dp[i][j][k] = true, то dp[i+r][j][k], dp[i][j+r][k], dp[i][j][k+r] = true. динамика, конечно, "с просмотром назад".

»
11 лет назад, # |
Rev. 3   Проголосовать: нравится -16 Проголосовать: не нравится

Можно написать такую динамику:
dp[i][mask][sum] — существует ли у маски mask из первых i гирек подмножество с суммой sum.
Переходы:
dp[i + 1][mask][sum] = true — не берём текущую гирьку в маску
dp[i + 1][mask|2i][sum] = true — берём гирьку в маску, но не берём в сумму
dp[i + 1][mask|2i][sum + m[i]] = true — берём гирьку в маску и в сумму.
Чтобы сэкономить память, будем хранить только динамику для предыдущего i.
Восстановление ответа понятно.
UPD: это заходит за 0.15, так что тоже имеет право на существование :)

»
11 лет назад, # |
  Проголосовать: нравится +34 Проголосовать: не нравится

Ограничение в 14 говорит нам "решайте за 3^N перебором подмасок маски".

Действительно, можно решать так, но можно это сделать еще лучше — у задачи есть классическое решение за N*2^N.

Посчитаем необходимый вес кучки. Если это нецелое число, то очевидно, что дела наши плохи) Далее задачу можно переформулировать так — можно ли разбить гирьки на 2 кучки, каждая из которых состоит из 2 кучек весом х?

Для каждой маски находим ее вес. Будем говорить, что маска хорошая, если ее вес х. Будем говорить, что маска очень хорошая, если у нее есть хорошая подмаска — для такой маски дополнительно будем хранить, какая именно ее подмаска является хорошей. Будем говорить, что маска вообще классная, если она очень хорошая и при этом ее вес 2*х. Все это считается очевидным способом за N*2^N, рассматривая маски от меньших к большим.

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

Теперь для решения изначальной задачи перебираем все возможные подмаски гирек, если подмаска вообще классная, и ее дополнение до полной маски — тоже, то мы нашли ответ. Очевидно, что он имеет вид: хорошая подмаска маски + остаток маски + хорошая подмаска дополнения + остаток дополнения.

Если ничего не нашли, то No nolution.

Я сабмитнул, работает за 0.005.