Могу ли я использовать динамическое программирование для решения этой проблемы?

Question

У меня очень мало опыта в динамическом программировании. Я использовал его для решения проблемы выравнивания ДНК, проблемы с основным рюкзаком и простой проблемы с поиском путей. Я понял, как они работают, но пока я не чувствую себя абсолютно комфортно.

У меня есть проблема, которая напоминает мне о динамическом программировании 0-1, но различия меня отбросили, и я не уверен, могу ли я по-прежнему использовать эту технику, или если мне придется согласиться на рекурсивный подход ,

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

Предположим, мне нужно выбрать комбо из тех предметов, которые являются самыми ценными, но остается в пределах веса и стоимости. До сих пор я описал проблему с рюкзаком, в значительной степени, с двумя ограничениями. Но вот разница:

Значение выбранного элемента изменяется в зависимости от того, сколько из них у меня есть в комбо.

Предположим, что каждый элемент имеет связанную с ним функцию, что говорит мне, какая группа этих предметов стоит мне. Это базовая линейная функция, такая как value_of_item = -3 (количество этого предмета) + 50

Так что, если у меня есть один элемент в комбо, то для меня это значение 47. Если бы у меня было 2 их, тогда они всего лишь 44 для меня.

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

Надеюсь, это имело смысл.

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

Answer 1

Если функции имеют вид

value(x, count) = base(x) - factor(x) * count, factor(x) > 0, 

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

x -> x_1 to x_max_count 
value_new(x_i) = value(x, i) 
weight(x_i) = weight(x) 

Теперь вы легко проверить, что не существует оптимального решения новых проблема использует некоторый предмет x_j, без использования каждого x_i с i < j.

Доказательство. Противоречие: предположим, что существует такое оптимальное решение S и оно использует x_j, но не x_i, j> i. Тогда существует альтернативное решение S ', которое использует x_i вместо x_j. Поскольку j> i,

value_new(x_j) = value(x, j) 
       = base(x) - factor(x) * j 
       < base(x) - factor(x) * i 
       = value(x, i) 
       = value_new(x_i) 

и, следовательно, S 'имеет более высокое значение, чем S, и мы достигли противоречия.

Кроме того, мы можем разрешить factor(x) = 0, это соответствует стандартным элементам ранца.

Однако, если существует ограничение формы

value(x, count) = base(x) + factor(x) * count 

где factor(x) это произвольное значение, решение выше не делает больше не будет работать, так как последний элемент будет тот, с наибольшим значением. Возможно, некоторая сложная модификация DP может позволить вам использовать такие ограничения, но я не вижу никаких изменений самой проблемы для использования DP сразу.

Некоторых исследования в этой теме (более общие):

• http://dept.cs.williams.edu/~heeringa/publications/knapsack.pdf
• http://clweb.csa.iisc.ernet.in/vsuresh/Kamesh-PLKP.pdf