Рюкзак с минимальной стоимостью

У меня есть несколько типов монет, у каждой есть вес (wi) и стоимость (ci). Итак, мне нужно сделать рюкзак весом == W и (!) Минимальной стоимостью монет в нем. Я не могу сделать повторение использования DP.


algorithm knapsack-problem dynamic-programming
person user2178460    schedule 17.03.2013    source источник
comment
Вы имеете в виду, что вам разрешено заводить отношения?   -  person jim mcnamara    schedule 17.03.2013
comment
Мне нужно завязать отношения или как я буду использовать DP без него?   -  person user2178460    schedule 17.03.2013

Ответы (1)


arrow_upward
1
arrow_downward

Просто сформулируйте обычное рекуррентное соотношение ...

Обозначьте минимальную стоимость, достижимую с общим весом k, как Min_cost (k).

Загрузите мемоизацию с помощью:

Min_cost(0) = cost of empty set = 0

Затем решите вопрос об увеличении значений k, используя:

Min_cost(i+1) = min [Min_cost(i)   + min [ci, for all items with wi = 1],
                     Min_cost(i-1) + min [ci, for all items with wi = 2],
                     Min_cost(i-2) + min [ci, for all items with wi = 3],
                     ...
                     Min_cost(2) + min [ci, for all items with wi = w-1],
                     Min_cost(1) + min [ci, for all items with wi = w],
                     Min_cost(0) + min [ci, for all items with wi = w+1]]
person Rahul Banerjee    schedule 17.03.2013
comment
И если нет элементов с текущим wi, как мне в этом случае найти min [ci, для всех элементов с wi = 1]? И, например, W = 100 и 2 типа элементов: w1 = 1 c1 = 1; w2 = 50 c2 = 30, поэтому здесь ответ должен быть 60, и я не могу получить его с помощью вашего алгоритма. Вы можете лучше объяснить свою идею? - person user2178460; 17.03.2013
comment
Если нет элемента с wi = 1, у вас не может быть строки Min_cost(i) + min [ci, for all items with wi = 1 в повторении, поскольку эти элементы не существуют. Что касается нескольких монет одного типа, существует ли бесконечное количество каждой из них? Если это так, отношение повторения будет выбирать только c1, пока вы не вычислите Min_cost (50), после чего оно переключится на c2, потому что Min_cost(50) = min[ Min_cost(49) + c1, Min_cost(0) + c2] = min[49 + 1, 0 + 30] = 30. При W = 90 вы получите Min_cost (100) = 60. Кстати, это похоже на назначение алгоритмов ... надеюсь, вы не используете StackOverflow для домашнего задания :) - person Rahul Banerjee; 17.03.2013