企业官网建设流程全解析

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[][]dp=newint[n][W+1];for(intj=weights[0];j<=W;j++){//初始化背包，物品数量为1时，背包容量满足时，价格始终为第一个物品价值（3）dp[0][j]=values[0];}for(inti=1;i<n;i++){//从第二个物品开始遍历for(intj=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];//不放入，即保持“同一背包容量下，放入上一个物品时的背包总价值”不变（且第一个物品的数值均已手动初始化，实现数据调用闭环）}}}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[]dp=newint[W+1];// 初始化：容量为0时价值为0dp[0]=0;// 动态规划过程for(inti=0;i<n;i++){// 遍历每个物品// 必须逆向遍历背包容量，防止重复计算for(intj=W;j>=weights[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[]dp=newint[W+1];// 初始化：容量为0时价值为0dp[0]=0;// 动态规划过程for(inti=0;i<n;i++){// 遍历每个物品// 必须逆向遍历背包容量，防止重复计算for(intj=0;j>=weights[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单元格：总背包价值