У меня есть несколько типов монет, каждый из которых имеет вес (wi) и стоимость (ci). Поэтому мне нужно сделать рюкзак с весом == W и (!) Минимальной стоимостью монет в нем. Я не могу сделать повторное отношение для использования DP.Рюкзак с минимальными затратами
Просто сформулировать обычное рекуррентное соотношение ...
Назначают минимальную стоимость достижимой общей веса к, как min_cost (к).
грузиться запоминанием с:
Min_cost(0) = cost of empty set = 0
Затем решить для увеличения значения к используя:
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]]
И если нет элементов с текущим wi, как я могу найти min [ci, для всех элементов с wi = 1] в этом случае? И для exaple W = 100 и 2 типа элементов: w1 = 1 c1 = 1; w2 = 50 c2 = 30, так что здесь ответ должен быть 60, и я не могу получить его с вашим algo. Можете ли вы объяснить свою идею лучше? – user2178460
Если нет элемента с wi = 1, вы не можете иметь 'Min_cost (i) + min [ci, для всех элементов с линией 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 для домашней работы :) –
Хорошо, теперь понятно. Благодарю. – user2178460
ли вы имеете в виду вы позволили сделать отношения? –
Мне нужно сделать отношение или как я буду использовать DP без него? – user2178460