算法索引01背包优化前空间优化版使用一维数组优化后的模拟流程图后面一张图有勘误为何优化后j不能使用正序遍历模拟流程图代码对应实现案例01背包优化前/** * 0-1背包问题解法与下方代码表格示例对应已模拟验证 * param W 背包的总容量示例8 * param weights 物品的重量数组示例[2, 3, 4, 5] * param values 物品的价值数组示例[3, 4, 5, 6] * param n 物品的总数量示例4 * return 能够装入背包的最大价值 */publicint[][]dp(intW,int[]weights,int[]values,intn){// 创建动态规划表dp[i][w]表示前i个物品在容量为w时的最大价值int[][]dpnewint[n][W1];for(intjweights[0];jW;j){//初始化背包物品数量为1时背包容量满足时价格始终为第一个物品价值3dp[0][j]values[0];}for(inti1;in;i){//从第二个物品开始遍历for(intj0;jW;j){//遍历每种背包容量if(jweights[i]){//当前遍历的物品可以放入背包因为j总背包容量 wt[i]当前物品重量//选择放入或不放入物品取价值的最大值dp[i][j]Math.max(dp[i-1][j],//不放入物品所以(总背包价值)不变dp[i-1][j-weights[i]]values[i]//放入物品1dp[i - 1][j - weights[i]].总背包容量减去wt[i]即j - wt[i]当前物品重量此时为剩余背包容量再看剩余背包容量的“背包总价值”例如剩余背包容量的“背包总价值”为0则直接添加当前物品的价值val[i]即下方代码示例表格的i1j3dp[1][3]的情况剩余背包容量的“背包总价值”为dp[0][0]即剩余背包容量的“背包总价值”为02 values[i].增加第i个物品的价值val[i]数组中即i);}else{//不可以放入背包dp[i][j]dp[i-1][j];//不放入即保持“同一背包容量下放入上一个物品时的背包总价值”不变且第一个物品的数值均已手动初始化实现数据调用闭环}}}returndp[n-1][W];//返回最后一个汇总的}空间优化版使用一维数组/** * 0-1背包问题解法已验证 * param W 背包的总容量示例8 * param weights 物品的重量数组示例[2, 3, 4, 5] * param values 物品的价值数组示例[3, 4, 5, 6] * param n 物品的总数量示例4 * return 能够装入背包的最大价值 */publicstaticintknapsackOptimized(intW,int[]weights,int[]values,intn){// 使用一维数组代替二维数组优化空间复杂度int[]dpnewint[W1];// 初始化容量为0时价值为0dp[0]0;// 动态规划过程for(inti0;in;i){// 遍历每个物品// 必须逆向遍历背包容量防止重复计算for(intjW;jweights[i];j--){// 更新dp[w]的值dp[j]Math.max(dp[j],// 不选当前物品dp[j-weights[i]]values[i]// 选择当前物品);}}returndp[W];// 返回最终结果}优化后的模拟流程图后面一张图有勘误为何优化后j不能使用正序遍历/** * 0-1背包问题解法已验证 * param W 背包的总容量示例8 * param weights 物品的重量数组示例[2, 3, 4, 5] * param values 物品的价值数组示例[3, 4, 5, 6] * param n 物品的总数量示例4 * return 能够装入背包的最大价值 */publicstaticintknapsackOptimized(intW,int[]weights,int[]values,intn){// 使用一维数组代替二维数组优化空间复杂度int[]dpnewint[W1];// 初始化容量为0时价值为0dp[0]0;// 动态规划过程for(inti0;in;i){// 遍历每个物品// 必须逆向遍历背包容量防止重复计算for(intj0;jweights[i];j){// 更新dp[w]的值dp[j]Math.max(dp[j],// 不选当前物品dp[j-weights[i]]values[i]// 选择当前物品);}}returndp[W];// 返回最终结果}模拟流程图代码对应实现案例设定w e i g h t s [ 2 , 3 , 4 , 5 ] weights[2,3,4,5]weights[2,3,4,5]v a l u e s [ 3 , 4 , 5 , 6 ] values [3,4,5,6]values[3,4,5,6]横轴j jj总背包容量纵轴i ii第i ii个物品d p dpdp单元格总背包价值i\j01234567800033333331003447777200345789930034578910