01背包

優化前

    /*** 0-1背包問題解法（與下方代碼表格示例對應，已模擬驗證）* @param W 背包的總容量（示例：8）* @param weights 物品的重量數組（示例：[2, 3, 4, 5]）* @param values 物品的價值數組（示例：[3, 4, 5, 6]）* @param n 物品的總數量（示例：4）* @return 能夠裝入背包的最大價值*/public int[][] dp(int W, int[] weights, int[] values, int n){// 創建動態規劃表，dp[i][w]表示前i個物品在容量為w時的最大價值int[][] dp = new int[n][W + 1];for(int j = weights[0]; j <= W; j++){ //初始化背包，物品數量為1時，背包容量滿足時，價格始終為第一個物品價值（3）dp[0][j] = values[0];}for(int i = 1; i < n; i++){ //從第二個物品開始遍歷for(int j = 0; j <= W; j++){ //遍歷每種背包容量if(j >= weights[i]){ //當前遍歷的物品可以放入背包，因為j（總背包容量）>= wt[i]（當前物品重量）//選擇放入或不放入物品，取價值的最大值dp[i][j] = Math.max(dp[i - 1][j], //不放入物品，所以(總背包價值)不變dp[i - 1][j - weights[i]] + values[i] //放入物品，1（dp[i - 1][j - weights[i]]）.總背包容量減去wt[i]（即j - wt[i]）（當前物品重量），此時為剩余背包容量，再看剩余背包容量的“背包總價值”；（例如，剩余背包容量的“背包總價值”為0，則直接添加當前物品的價值val[i]，即下方代碼示例表格的i=1，j=3（dp[1][3]）的情況，剩余背包容量的“背包總價值”為dp[0][0]，即剩余背包容量的“背包總價值”為0）2（+ values[i]）.增加第i個物品的價值val[i]（數組中即i）);}else{ //不可以放入背包dp[i][j] = dp[i - 1][j]; //不放入，即保持“同一背包容量下，放入上一個物品時的背包總價值”不變（且第一個物品的數值均已手動初始化，實現數據調用閉環）}}}return dp[n - 1][W]; //返回最后一個匯總的
}

空間優化版（使用一維數組）

    /*** 0-1背包問題解法（已驗證）* @param W 背包的總容量（示例：8）* @param weights 物品的重量數組（示例：[2, 3, 4, 5]）* @param values 物品的價值數組（示例：[3, 4, 5, 6]）* @param n 物品的總數量（示例：4）* @return 能夠裝入背包的最大價值*/
public static int knapsackOptimized(int W, int[] weights, int[] values, int n) {// 使用一維數組代替二維數組，優化空間復雜度int[] dp = new int[W + 1];// 初始化：容量為0時價值為0dp[0] = 0;// 動態規劃過程for (int i = 0; i < n; i++) { // 遍歷每個物品// 必須逆向遍歷背包容量，防止重復計算for (int j = W; j >= weights[i]; j--) {// 更新dp[w]的值dp[j] = Math.max(dp[j], // 不選當前物品dp[j - weights[i]] + values[i] // 選擇當前物品);}}return dp[W]; // 返回最終結果}

優化后的模擬流程圖

為何優化后，j不能使用正序遍歷

    /*** 0-1背包問題解法（已驗證）* @param W 背包的總容量（示例：8）* @param weights 物品的重量數組（示例：[2, 3, 4, 5]）* @param values 物品的價值數組（示例：[3, 4, 5, 6]）* @param n 物品的總數量（示例：4）* @return 能夠裝入背包的最大價值*/
public static int knapsackOptimized(int W, int[] weights, int[] values, int n) {// 使用一維數組代替二維數組，優化空間復雜度int[] dp = new int[W + 1];// 初始化：容量為0時價值為0dp[0] = 0;// 動態規劃過程for (int i = 0; i < n; i++) { // 遍歷每個物品// 必須逆向遍歷背包容量，防止重復計算for (int j = 0; j >= weights[i]; j++) {// 更新dp[w]的值dp[j] = Math.max(dp[j], // 不選當前物品dp[j - weights[i]] + values[i] // 選擇當前物品);}}return dp[W]; // 返回最終結果}

模擬流程圖

代碼對應實現案例

設定$weights=[2,3,4,5]$，$values=[3,4,5,6]$
橫軸：$j$（總背包容量）；縱軸：$i$（第$i$個物品）；$dp$單元格：總背包價值

i\j	0	1	2	3	4	5	6	7	8
0	0	0	3	3	3	3	3	3	3
1	0	0	3	4	4	7	7	7	7
2	0	0	3	4	5	7	8	9	9
3	0	0	3	4	5	7	8	9	10