01背包与完全背包学习总结

背包问题分类见下图

参考学习点击：代码随想录01背包讲解

01背包问题：

核心思路：

1、先遍历物品个数，再遍历背包容量。因为容量最先是最大的，往背包里放物品，所以背包容量在慢慢减少，但背包容量需要大于每一个物品体积

2、每个物品有2个选择：选中和不选中。

3、选中的结果是背包剩余容量的最大价值+选中物品的价值；

4、不选中的结果是背包剩余容量还是不变，最大价值还是背包剩余容量的最大价值

 public static void main(String[] args) {int[] weight = {1, 3, 4};  //每个物品体积int[] value = {15, 20, 30}; // 每个物品价值int bagWight = 4;            // 背包容量testWeightBagProblem(weight, value, bagWight);}public static void testWeightBagProblem(int[] weight, int[] value, int bagWeight){//定义dp数组：dp[j]表示背包容量为j时，能获得的最大价值int[] dp = new int[bagWeight + 1];//背包容量来定义dp数组for (int i = 0; i < weight.length; i++){ //先遍历物品for (int j = bagWeight; j >= weight[i]; j--){ //再遍历背包，背包容量是从最大一直慢慢减少          //每个物品有2种选择，选中与不选中：选中的话，背包价值=背包容量剩余物品的价值在加上选中物品的价值//不选中的话，背包价值=背包容量j的价值dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);}}//打印dp数组for (int j = 0; j <= bagWeight; j++){System.out.print(dp[j] + " ");}}

完全背包问题：