请人做个网页大概需要多少钱_跨境电商可不可靠_百度运营公司_沈阳网站关键词排名

这里写自定义目录标题

完全背包
- 优化前
- - 代码
  - 优化空间前的模拟流程图
- 空间优化版（使用一维数组）
- - 代码
  - 优化空间后的模拟流程图
- 代码对应实现案例

完全背包

与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时价值为0for(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]; // 返回最终结果}

优化空间后的模拟流程图