江苏专业网站建设费用,网站右侧 回到顶部,网站建设 模仿阿里云官网,国家认可的赚钱游戏无广告学习目标#xff1a; 动态规划五部曲#xff1a; ① 确定dp[i]的含义 ② 求递推公式 ③ dp数组如何初始化 ④ 确定遍历顺序 ⑤ 打印递归数组 ---- 调试 引用自代码随想录#xff01; 60天训练营打卡计划#xff01;
学习内容#xff1a;
二维数组处理01背包问题
听起来…学习目标 动态规划五部曲 ① 确定dp[i]的含义 ② 求递推公式 ③ dp数组如何初始化 ④ 确定遍历顺序 ⑤ 打印递归数组 ---- 调试 引用自代码随想录 60天训练营打卡计划
学习内容
二维数组处理01背包问题
听起来思路很简单但其实一点也不好实现。动态规划五步曲 ① 确定dp[i][j]的含义 任取[0, i]的物品后放进容量为j的背包 所能放的 最大价值 ② 求递推公式 dp[i][j] max(dp[i-1][j] , dp[i-1][ j - weight[i] ] value[i]) Ⅰ 不放物品 i dp[i-1][j] Ⅱ 放物品 i : dp[i-1][j - weight[i]] value[i] ③ dp数组如何初始化 按下表的第一行和第一列赋值其中箭头都是继承来的值画圈的表示自己取得了最大值。 ④ 确定遍历顺序 先物品后背包行 / 先背包后物品列
import java.util.Scanner;public class Main {public static void main(String[] args) {//m,n分别代表物品种类和背包容量int itemSize 0,bagSize 0;Scanner sc new Scanner(System.in);//获取itemSize和bagSize的值itemSize sc.nextInt();bagSize sc.nextInt();//初始化对应的重量数组和价值数组int[] weight new int[itemSize];int[] value new int[itemSize];//这两个都是物品的属性大小只和物品数量有关for(int i 0;i itemSize;i){weight[i] sc.nextInt();}for (int i 0;i itemSize;i){value[i] sc.nextInt();}// int[] weight {1,3,4};// int[] value {15,20,30};// int bagSize 4;testWeightBagProblem(weight,value,bagSize);}/*** 动态规划获得结果* param weight 物品的重量* param value 物品的价值* param bagSize 背包的容量*/public static void testWeightBagProblem(int[] weight, int[] value, int bagSize){int itemSize weight.length;// dp数组的含义是在[0,i]件物品中选择是否放入背包 的 最大价值int[][] dp new int[itemSize][bagSize1];// 初始化dp数组默认都为0.// 只放一件物品时的初始化for(int j weight[0]; j bagSize1; j){dp[0][j] value[0];}// 正常的为dp数组赋值依赖左上位置的其他的dp值for(int i 1; i itemSize; i){// j是背包容量for(int j 1; j bagSize1; j){// 如果容量不够放入新的物品则从上一行继承if(j weight[i]) dp[i][j] dp[i-1][j];// 如果容量可以放入新的物品则从上一行的左侧继承elsedp[i][j] Math.max(dp[i-1][j], dp[i-1][j-weight[i]] value[i]);}}System.out.println(dp[itemSize-1][bagSize]);// 打印dp数组// for (int i 0; i goods; i) {// for (int j 0; j bagSize; j) {// System.out.print(dp[i][j] \t);// }// System.out.println(\n);// }}
}
一维数组处理01背包问题
动态规划五步曲 ① 确定dp[j]的含义 任取物品放进容量为j的背包 所能放的 最大价值 ② 求递推公式 dp[j] max(dp[j] , dp[j - weight[i]] value[i]) Ⅰ 不放物品 i dp[j] Ⅱ 放物品 i : dp[j - weight[i]] value[i] ③ dp数组如何初始化 初始值全部附0长度为容量的长度加1j1 ④ 确定遍历顺序 必须先物品后背包行且便利背包大小时必须使用倒序的顺序遍历。为了防止一个物品被使用多次倒叙遍历时相同的物品仅能被取用一次 import java.util.Scanner;public class Main {public static void main(String[] args) {//m,n分别代表物品种类和背包容量int itemSize 0,bagSize 0;Scanner sc new Scanner(System.in);//获取itemSize和bagSize的值itemSize sc.nextInt();bagSize sc.nextInt();//初始化对应的重量数组和价值数组int[] weight new int[itemSize];int[] value new int[itemSize];//这两个都是物品的属性大小只和物品数量有关for(int i 0;i itemSize;i){weight[i] sc.nextInt();}for (int i 0;i itemSize;i){value[i] sc.nextInt();}// int[] weight {1,3,4};// int[] value {15,20,30};// int bagSize 4;testWeightBagProblem(weight,value,bagSize);}/*** 动态规划获得结果* param weight 物品的重量* param value 物品的价值* param bagSize 背包的容量*/public static void testWeightBagProblem(int[] weight, int[] value, int bagSize){// 创建dp一维数组int goods weight.length; // 获取物品的数量int[] dp new int[bagSize 1];// 初始化dp数组// 创建数组后其中默认的值就是0// 填充dp数组for (int i 0; i goods; i) {// 必须使用倒叙遍历背包大小for (int j bagSize; j 0; j--) {// 防止越界错误if (j weight[i]) {dp[j] dp[j];} else {dp[j] Math.max(dp[j] , dp[j-weight[i]] value[i]);}}}System.out.print(dp[bagSize]);// 打印dp数组// System.out.print(dp[goods-1][bagSize] \n);// for (int i 0; i goods; i) {// for (int j 0; j bagSize; j) {// System.out.print(dp[i][j] \t);// }// System.out.println(\n);// }}
} 学习时间
上午两个半小时整理文档半小时。
