思路: 子问题:第j体积状态(小于或等于)下最大价值=第j -1体积状态下第i件物品的可装入或者不可装入两种情况中的最大值
public class 背包问题 { static Thing[] things ; static int[] dp ; public static void main(String[] args) { //记录输入 Scanner sc = new Scanner(System.in); int pack_max =sc.nextInt(); //背包体积最大值 int thing_max =sc.nextInt(); //物品总数 things =new Thing[thing_max +1]; dp =new int[pack_max +1]; //初始化每一种体积状态下的价值为‘0’ for(int i =1 ;i <=thing_max ;i ++) {things[i] =new Thing(sc.nextInt() ,sc.nextInt());} sc.close(); //递推遍历所有物品 for(int i =1 ;i <=thing_max ;i ++) { for(int j =pack_max ;j >=things[i].tiji ;j --) //子问题分解，倒序遍历,保证dp[j]均只被修改一次 //转移方程 dp[j] =Math.max(dp[j], dp[j -things[i].tiji] +things[i].val); } //输出结果 System.out.println(dp[pack_max]); } } class Thing{ int tiji; //体积 int val; //价值 public Thing(int tiji, int val) { super(); this.tiji = tiji; this.val = val; } } 完全背包问题 已知:普通背包问题条件下,每i件物品的数量都可以是多个的(可视为物品总数是无限多的)求解:背包最大的总的价值思路: 重复遍历第i件物品->dp[j]应实时修改以取得最大值
public class 完全背包 { static Thing[] things ; static int[] dp ; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int pack_max =sc.nextInt(); int thing_max =sc.nextInt(); things =new Thing[thing_max +1]; dp =new int[pack_max +1]; for(int i =1 ;i <=thing_max ;i ++) {things[i] =new Thing(sc.nextInt() ,sc.nextInt());} sc.close(); for(int i =0 ;i <=thing_max ;i ++) dp[i] =0; for(int i =1 ;i <=thing_max ;i ++) { for(int j =things[i].tiji ;j <=pack_max ;j ++) //正序遍历物品,dp[j]将被实时修改为j体积状态下的最大值 dp[j] =Math.max(dp[j], dp[j -things[i].tiji] +things[i].val); } System.out.println(dp[pack_max]); } }参考: 简单的动规实现案例-三角形 背包问题 王国的故事-动规的实现需要考虑的要素
