Правильно ли мое рекуррентное отношение для суммы подмножества?

Правильно ли это рекуррентное соотношение для задачи о сумме подмножеств?
Утверждение: Выведите «Да» или «Нет» в зависимости от того, существует ли подмножество данного массива a [], которое суммируется до заданного числа п.

dp [i] [j] = true, если от 0 до j элементы в массиве в сумме дают i и false в противном случае.

dp [i] [j] = min (dp [i-a [j]] [j], dp [i] [j-1])

Значения базового случая:
dp [0] [0] = true
dp [1 ... i] [0] = false

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


recurrence dynamic-programming subset-sum
person newbie_old    schedule 22.02.2015    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Вы почти правы (не уверен, почему вы использовали min). Но пусть dp [i] [j] хранит ответ о том, является ли подмножество arr [0], arr [1], .... arr [j] ( здесь arr [] - массив элементов) можно суммировать до i. То есть dp [i] [j] равно 1, если ответ «да», и 0, если ответ отрицательный. Игнорируя базовые случаи, рекуррентное соотношение: dp [i] [j] = (dp [i] [j-1] | dp [i-arr [j]]] [j-1]) . Чтобы получить точный код, базовые случаи и реализацию, вы можете посмотреть здесь: http://www.geeksforgeeks.org/dynamic-programming-subset-sum-problem/.

person sashas    schedule 23.02.2015
comment
О, мин было ошибкой. Думаю, я понял, почему dp [ia [j]] [j-1] прав: предположим, что у нас есть только два элемента [1, 4], поэтому dp [5] [2] = dp [5-4] [2-1 ] = dp [1] [1], что означает сумму 1 только с одним элементом, если это правда, то dp [5] [2] также верно. - person newbie_old; 23.02.2015
comment
@newbie_old так я ответил на ваш вопрос или вам не понятно? Если он ответил на ваш вопрос, вы можете принять его - person sashas; 23.02.2015
comment
спасибо за ответ и извините за то, что не принял его раньше, но просто хотел узнать ваше мнение о моих комментариях. - person newbie_old; 23.02.2015
comment
@newbie_old конечно. Я думал, вы не задаете вопрос. Да, в вашем примере dp [5] [2] = (dp [5-4] [2-1] | dp [5] [1]) теперь dp [5] [1] ложно, но dp [1] [1] ] верно и, следовательно, dp [5] [2] также верно. Надеюсь, я ответил на ваш вопрос. - person sashas; 23.02.2015