通過動態編程解決具有多個約束的揹包（0,1）

Question

假設我有一個具有權重w和值v的對象的集合，我想最大化所選對象的值的總和而不用其權重的總和超過最大W.直到現在，經典的揹包問題。

現在假設每個對象都可以屬於類別A，B，C等等......現在我想讓我的解決方案中的對象尊重A，B，C等的確切數目。我要求我算法，否則返回最近的解決方案。

實施例：

Object 1 : w=4 v=16 Type A 
Object 2 : w=3 v=15 Type A 
Object 3 : w=2 v=5 Type A 
Object 4 : w=1 v=2 Type A 
Object 5 : w=1 v=4 Type B 
Object 6 : w=2 v=4 Type B 
Object 7 : w=2 v=3 Type B 
Object 8 : w=4 v=9 Type B 
Object 9 : w=3 v=9 Type B 
Object 10: w=1 v=2 Type B 
Object 11: w=1 v=4 Type B 
Object 12: w=4 v=8 Type C 
Object 13: w=8 v=19 Type C 
Object 14: w=1 v=2 Type C 
Object 15: w=3 v=5 Type C 

Desired number of objects : A=2 B=5 C=2 

Set of objects solution : A{1,2},B{5,6,7,9,11},C{13,15} 

我的第一種方法是考慮multidimensionnal陣列，其中所述第一尺寸爲對象的數目，則第二最大W，而其它維度中的每個類別的所需要的期望的數字，並且在用動態規劃填充陣列之後，如果對象屬於某個類別，則權重爲1，否則爲0。它不起作用，因爲有時某些解決方案更適合用以下的對象。

我的第二種方法是找到一個類別中所需數量的對象的每個可能子集，並在常規動態算法中將它們用作實例之後。它有效，但似乎不雅。

任何想法？

Answer 1

只有兩個維度數組是可以的。

首先，應用一個名爲dp[n][m]的數組，其中第一維是對象的數量，第二維是w的總和。 dp[i][j]的值是v的最大值，其中第一個i對象和當前權重爲j。

我們可以得到以下關係式：dp[i][j] = max (dp[i][j], dp[i-1][j-w] + v)其中w是i-th對象和v的重量是i-th對象的值。

你的答案是max (dp[n][j] | 0<=j<=W)

UPD1：

我沒在意類別，你可以爲每個類別做

UPD2：

對不起，我我以前不看對象數量限制，我們可以用3維的數組來代替。只需撥打dp[n][k][m]其中k是選擇的對象數，n和m像以前一樣。

公式更改爲dp[i][j][k] = max (dp[i][j][k], dp[i-1][j-1][k-w] + v)

答案是max (dp[n][k][j] | 0<=j<=W)其中k是你的次數限制。