動态規劃-03多重背包

緊接前面一篇，講一下“多重背包”問題，該問題與“完全背包”相比，在每個物品的選取次數上給出了限定，即選取次數k不能無限的增大，其方程和“完全背包”的極度相似，隻是k的限定條件發生了變化。

c[i][j] = max(c[i-1][j-(k*w[i-1])] + k*v[i-1], c[i-1][j]) (0 <= k <= counts[i])
           

其中，counts[i]表示第i件物品可選取的次數。

假設：定義可容納總重量W =10 Kg，物品種類 N = 4，每件物品重量w[i]，對應價值v[i]，求解在可容納重量範圍内如何選取可獲最大價值。

本題具體題目：

可能出現的情況：

以上表格同樣是從左到右、從上到下生成，具體實作代碼如下：

//一維數組實作多重背包問題，注意其中的二分法劃分
	private static int[] BP_method03_1D(int m,int n,int[] w,int[] v,int[] counts){
		int c[] = new int[m+1];
		for (int i = 0; i < m+1; i++) {
			c[i] = 0;//不必完全裝滿，則全部初始化為0
		}
		for (int i = 0; i < n; i++) {
			//過濾掉次數小于2的物品
			for(int k = 1; k < counts[i]; k <<= 1){
					for (int j = m; j >= k * w[i]; j--) {//限定總重量
						c[j] = Math.max(c[j-k*w[i]] + k*v[i], c[j]); 
					}
				counts[i] -= k;
			}
			//此處為次數為1的物品
			for (int j = m; j >= w[i]; j--) {//限定總重量
					c[j] = Math.max(c[j-w[i]] + v[i], c[j]); 
			}
		}
		return c;
	}
           

//二維數組實作，此處代碼和前一篇“完全背包”二維數組方法中的源碼基本一樣，僅是k的取值由‘k*w[i-1] <= m’變為‘k <= counts[i]’
	private static int[][] BP_method03_2D(int m,int n,int[] w,int[] v,int[] counts){
		int c[][] = new int[n+1][m+1];
		List<Integer> list = new ArrayList<>(); 
		for (int i = 0; i < n+1; i++) {
			c[i][0] = 0;
		}
		for (int i = 0; i < m+1; i++) {
			c[0][i] = 0;
		}
		for (int i = 1; i <= n; i++) {//限定物品種類，無重複
			for (int j = 1; j <= m; j++) {//限定總重量
				list.clear();
				for (int k = 0; (k <= counts[i-1]) && (k >= 0); k++) {
					if (j >= k*w[i-1]) {
						list.add( Math.max(c[i-1][j-(k*w[i-1])] + k*v[i-1], c[i-1][j]));
					}
				}
				c[i][j] = Collections.max(list);
			}
		}
		return c;
	}
           

其輸出結果如下：

一維選取：
0 0 5 5 10 10 13 14 16 17 17  
二維選取：
0  3  3  6  6  6  6  6  6  6  
0  3  4  6  7  7  10  10  10  10  
0  5  5  10  10  13  14  16  17  17  
0  5  5  10  10  13  14  16  17  17