纯个人整理，蓝桥杯使用的算法模板day2（0-1背包问题），手打个人理解注释，超全面，且均已验证成功（附带详细手写“模拟流程图”，全网首个

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