最低成本的揹包

我有幾種類型的硬幣，每種都有重量（wi）和成本（ci）。所以我必須做一個揹包，重量== W和（！）硬幣的最低成本。我不能讓使用DP的復發關係。最低成本的揹包

2013-03-17 user2178460

你的意思是你被允許做的關係？ – 2013-03-17 03:23:08

我必須做一個關係，或者如何在沒有它的情況下使用DP？ – user2178460 2013-03-17 03:25:26

就制定通常遞推關係...

標明用總重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]]

來源

2013-03-17 04:32:21

如果沒有當前wi的元素，在這種情況下如何找到min [ci，對於wi = 1的所有項目]？例如W = 100和2種類型的項目：w1 = 1 c1 = 1; w2 = 50 c2 = 30，所以這裏的答案應該是60，我不能用你的算法得到它。你能更好地解釋你的想法嗎？ – user2178460 2013-03-17 07:51:39

如果沒有wi = 1的項目，那麼對於重複中所有wi = 1行的項目，您不能擁有Min_cost（i）+ min [ci，因爲這些項目不存在。至於相同類型的多個硬幣，每個硬幣的數量是多少？因爲Min_cost（50）= min [Min_cost（49）+ c1，Min_cost（0）+ c2），直到你計算Min_cost（50），此時它將切換到c2， ] = min [49 + 1,0 + 30] = 30'。在W = 90時，你會得到Min_cost（100）= 60。順便說一下，這看起來像一個算法分配...希望你沒有使用StackOverflow作業:) – 2013-03-17 08:04:56

好吧，現在已經很清楚了。謝謝。 – user2178460 2013-03-17 08:14:32

最低成本的揹包

回答

相關問題