形成背景問題變化的動態規劃算法

所以我在想，形成背景問題變化的動態規劃算法

我想對揹包問題做一個變化。

想象一下原來的問題，具有不同重量/價值的物品。

我的版本將與正常的權重/值一起包含「組」值。

例如。項目1 [5KG，$ 600電子] 項目2 [1KG，$ 50食品]

現在，有一組這樣的項目，我將如何編寫了揹包問題，以確保從最多1項選擇每個「組」。

注：

你並不需要從該組中選擇一個項目
有各組
你還在重量最小化在多個項目，實現價值最大化
的預定義的組的數量以及它們的值。

我只是在這個階段寫了一個代碼草稿，而且我選擇了使用動態方法。我理解常規揹包問題的動態解決方案背後的想法，我如何改變這個解決方案以合併這些「組」？

KnapSackVariation(v,w,g,n,W) 
{ 
    for (w = 0 to W) 
    V[0,w] = 0; 
    for(i = 1 to n) 
    for(w = 0 to W) 
     if(w[i] <= w) 
      V[i,w] = max{V[i-1, w], v[i] + V[i-1, w-w[i]]}; 
     else 
      V[i,w] = V[i-1, w]; 
    return V[n,W]; 
}

這是我到目前爲止，需要補充它，這樣它會刪除它是每一個它解決了這次在組中的所有相關項目。

來源

2011-10-07 user730882

將羣組項添加到狀態！ – quasiverse

解決它作爲一個組合優化問題呢？對於每件商品，您可以選擇一件商品或者不選擇商品。您可能想使用分支和界限搜索來解決它。 – ysdx

假設
C [1]：第i個元素
V [I，W，S]的類別：揹包，使得其包含在最大一個項目從S中

每個類別的最大值

Recursive Formulation 
V[i,w,S] = max(V[i-1,w,S],V[i,w-w[i],S-{c[i]}] + v[i]) 
Base Case 
V[0,w,S] = -`infinity if w!=0 or S != {}`

來源

2011-10-09 16:28:27 gibraltar

剛剛注意到你的問題，試圖找到我自己的問題的答案。你所說的問題是一個衆所周知的，被廣泛研究的問題，稱爲多重選擇揹包問題。如果你google了，你會發現各種各樣的信息，我也可以推薦這本書：http://www.amazon.co.uk/Knapsack-Problems-Hans-Kellerer/dp/3642073115/ref=sr_1_1?ie=UTF8&qid=1318767496&sr=8-1，它專門研究了這個問題。在MCKP的經典配方中，您必須從每個組中選擇一個項目。但是，您可以輕鬆地將該版本的問題轉換爲您的版本，方法是向利潤和權重= 0的每個組添加一個虛擬項目，並使用相同的算法。我會告誡你不要試圖通過一些調整來修改二進制揹包問題的代碼給MCKP - 這種方法很可能會導致你找到一個解決方案，隨着每個組中項目數量的增加，性能會下降到令人無法接受的程度。

來源

2011-10-16 12:25:23 Karen

形成背景問題變化的動態規劃算法

回答

相關問題