前面4篇部落格已經将幾種基礎背包問題介紹,本文主要對“二維費用”背包問題進行介紹。“二維費用”背包問題,較前面幾種背包問題主要是對每類物品增加了一維費用,用一個簡單的例子來說,即選取某一個物品的同時增加了一個附屬物品,同時對附屬物品的費用也有了限制,通過這種思維,可以将“二維費用”背包轉換為“01基礎背包”問題,按照“01基礎背包”方程可以得到該基礎方程:
c[i][j][k] = max(c[i-1][j-w[i-1]][k-w2[i-1]] + v[i-1], c[i-1][j][k]);
該方程隻是在”01基礎背包“方程的基礎上增加了一維,其代碼實作也較為簡單,以下将通過一個具體的例子來說明。
假設:在選取a、b、c三種物品放入背包時,每類物品由于均有附屬物,是以對主件和附件均有容量要求,主件容量要求不超過8 Kg,而附件容量不超過5 Kg,在該限制條件下,求可以擷取的最大價值。
具體題目如下:
可能出現的情況:
上述表格由上到下、由左到右生成,由于主件、附件捆綁在一起,是以在選取時需要雙重考慮。其Java實作代碼如下:
//在01基礎背包的基礎上,添加一維數組來進行多重考慮
private static int[][] BP_method05_1D(int m,int m2,int n,int[] w,int[] w2,int[] v){
int c[][] = new int[m+1][m2+1];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
c[i][j] = 0;
}
}
for (int i = 0; i < n; i++) {//限定物品種類,無重複
for (int j = m; j >= w[i]; j--) {//限定主件總重量
for (int k = m2; k >= w2[i]; k--) {//限定附件重量
c[j][k] = Math.max(c[j-w[i]][k-w2[i]] + v[i], c[j][k]);
}
}
}
return c;
}
//因為新增加了一維判斷,是以在原來的二維解法基礎上形成三維解法
private static int[][][] BP_method05_2D(int m1,int m2,int n,int[] w, int[] w2,int[] v){
int c[][][] = new int[n+1][m1+1][m2+1];
for (int i = 0; i < n+1; i++) {
c[i][0][0] = 0;
}
for (int i = 0; i < n; i++) {
c[0][i][0] = 0;
}
for (int i = 1; i <= n; i++) {//限定物品種類,無重複
for (int j = 1; j <= m1; j++) {//限定主件總重量
for (int k = 0; k <= m2; k++) {//限定附件總重量
if (j >= w[i-1] && k >= w2[i-1]) {
c[i][j][k] = Math.max(c[i-1][j-w[i-1]][k-w2[i-1]] + v[i-1], c[i-1][j][k]);
}else {
c[i][j][k] = c[i-1][j][k];
}
}
}
}
return c;
}
其輸出結果如下:
二維解法:
0 0 0 0 0
0 0 0 0 0
0 4 4 4 4
0 4 4 5 5
0 4 6 6 6
0 4 6 6 6
0 4 6 6 6
0 4 6 6 10
三維解法:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 4 4 4 0 0 4 4 4 4 0 0 4 4 4 4 0 0 4 4 4 4 0 0 4 4 4 4 0 0 4 4 4 4
0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 4 4 4 0 0 4 4 5 5 0 0 4 4 5 5 0 0 4 4 5 5 0 0 4 4 5 5 0 0 4 4 5 5
0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 4 4 4 0 0 4 4 5 5 0 0 4 6 6 6 0 0 4 6 6 6 0 0 4 6 6 6 0 0 4 6 6 10