揹包算法變化

我有以下問題：揹包算法變化

有一組項目，每個項目有2個不同的正值A和B.

揹包有兩個值：總量a和共計b。這是所選項目的值A和B的最大總和。

我必須知道，揹包可以容納的最大物品數量是多少。

實施例：

輸入：

總量a：10，共計b：15

ITEM1甲：3，B：4

ITEM2答：7，B： 2

item3 A：1，B：9

ITEM4答：2，B：1

ITEM5答：4，B：6

輸出：

3（項目：2，3，4）

如何我應該使用動態編程來解決這個任務嗎？

來源

2013-11-26 Mariusz

可能重複http://stackoverflow.com/questions/14103846/trying-to-figure-out-the-classic-knapsack-recurrence/14103876#14103876 或的http：//計算器。com/questions/14137267/can-not-understand-knapsack-solutions/14142580＃14142580 –

您鏈接的帖子包含經典揹包問題的答案，其中每個項目都有其重量和價值。在我的情況下，物品沒有價值，但他們有兩個重量。 – Mariusz

這被稱爲「多約束揹包問題」（MKP，偶爾呈現爲d-KP）。它可以像普通揹包問題那樣在假多項式時間內解決，但是您需要一個二維表格而不是一個表格。

來源

2013-11-26 10:14:17 Sneftel

定義米[I，WA，WB]爲最大的值（這裏項目計數），即可以達到與a S爲小於或等於wa和總和的b S爲小於或總和相當於wb，使用項目最多i。

m[i,wa,wb] = m[i-1,wa,wb]

如果item[i].a > wa或item[i].b > wb

或

m[i,wa,wb] = max (m[i-1, wb, wb], m[i-1, wa - item[i].a, wb - item[i].b] + 1)

如果item[i].a <= wa和item[i].b <= wb

來源

2013-11-26 10:53:10 chill

非常感謝！ – Mariusz

這裏是一個遞推方程，可以幫助你： -

if(Items[N].b<=Wa && Items[N].b<=Wa) 
    Value(N,Wa,Wb) = max(1+Value(N-1,Wa-Items[N].a,Wb-Items[N].b),Value(N-1,Wa,Wb)) 

else Value(N,Wa,Wb) = Value(N-1,Wa,Wb) 

Where Wa = Current capacity of A sack & Wb of B sack 
     N = no of items considered

注意：您可以在遞歸解決方案上使用散列表實現，以防止三維數組。

來源

2013-11-26 10:58:09

揹包算法變化

回答

相關問題