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

完全背包

与01背包代码对别不同点，存在如以下注释区别，使之实现重复选择该物品
查阅了几乎网上所有资料，均只指出与01背包在状态转移方程的区别，且没有统一问题背景，造成初学者难以区分二者的所有实质性不同，以及相同问题背景下的不同求解结果。
基于此背景，作者以个人理解为主，专门设立统一问题背景，并标注出所有不同（代码注释形式，仅针对标注修改的行，未标注修改的，均与01背包代码保持一致），以及各个不同处所产生的实际功能
—》且附带模拟流程图，保证实际应用绝对正确，大家也可学习作者是如何进行模拟，期待能够帮助你
（ps：模拟太容易写错了，因此有部分涂改，请见谅，但可保证改正后的一定正确）

优化前

代码

与01背包代码相比，共两处不同

    /**
     * 0-1背包问题解法（与下方代码表格示例对应，已模拟验证）
     * @param W 背包的总容量（示例：8）
     * @param weights 物品的重量数组（示例：[2, 3, 4, 5]）
     * @param values 物品的价值数组（示例：[3, 4, 5, 6]）
     * @param n 物品的总数量（示例：4）
     * @return 能够装入背包的最大价值
     */
//i的含义更改，

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++){
		dp[0][j] = dp[0][j - weights[0]] + values[0]; //修改①：初始化中for循环的内部逻辑修改，由“dp[0][j] = values[0]”修改为“dp[0][j] = dp[0][j - weights[0]] + values[0]”。物品0可无限选，只需背包容量满足即可。（如：dp[0][4] = dp[0][2] + 3 = 3 + 3 -> 6，结果分析：只有物品0时，因为背包容量为4，此时可共重复放置2个物品0，因此总价值为6）
	}
	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][j - weights[i]] + values[i] //修改②：修改第一个维度[i-1]为[i]。第一个维度的[i]实现重复选择该物品，而不是退回选择[i - 1]（上一个物品），再判断重复选此物品，与不放入物品的价值，取最大值
				);
			}else{ //不可以放入背包
				dp[i][j] = dp[i - 1][j]; //不放入，即保持“同一背包容量下，放入上一个物品时的背包总价值”不变（且第一个物品的数值均已手动初始化，实现数据调用闭环）
			}
		}
	}

	return dp[n - 1][W]; //返回最后一个汇总的
}

优化空间前的模拟流程图

空间优化版（使用一维数组）

此时可允许重复选择物品，因此j采取正向遍历（与01背包的逆向遍历不同）

代码

    /**
     * 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时价值为0
		for(int j = weights[0]; j <= W; j++){ //物品0可无限选，只需背包容量满足即可
			dp[j] = dp[j - weights[i]] + values[i];
		}
        
        // 动态规划过程
        for (int i = 1; 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$单元格：总背包价值