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

雨点打透心脏的1/2处 2024-02-17 09:09 20阅读 0赞

背包问题分类见下图

![0185d77fbb7749d4abffe492a45936ca.png][]

参考学习点击：[代码随想录01背包讲解][01] [完全背包讲解][Link 1]

### 01背包问题： ###

01背包问题就是有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight\[i\]，得到的价值是value\[i\] 。**每件物品只有一个（也就是只能放入背包一次）**，求解将哪些物品装入背包里物品价值总和最大。

> 核心思路：
> 
> 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] + " ");
            }
        }

### 完全背包问题： ###

完全背包问题就是有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight\[i\]，得到的价值是value\[i\] 。**每件物品都有无限个（也就是可以放入背包多次）**，求解将哪些物品装入背包里物品价值总和最大。

> 核心思路：
> 
> 1、先遍历物品个数，再遍历背包容量。因为完全背包中物品可以选取任意次，所以遍历背包需要从小到大开始遍历，从第一个物品的容量开始遍历
> 
> 2、每个物品可以选择任意次或者不选中
> 
> 3、选中的结果是背包剩余容量的最大价值+选中物品的价值；
> 
> 4、不选中的结果是背包剩余容量还是不变，最大价值还是背包剩余容量的最大价值

> **完全背包和01背包问题不同的地方就是：**
> 
> **1、****完全背包****中每种物品有无限件，可以****取任意次或者不取****，而****01背包****问题中物品****只有取一次或者不取两个选择**
> 
> **2、01背包中遍历背包体积的顺序是****从大到小****，完全背包中遍历背包体积的顺序是****从小到大**

//先遍历物品，再遍历背包
    private static void testCompletePack(){
        int[] weight = {1, 3, 4};
        int[] value = {15, 20, 30};
        int bagWeight = 4;
    
        int[] dp = new int[bagWeight + 1];
        for (int i = 0; i < weight.length; i++){ // 先遍历物品
            for (int j = weight[i]; j <= bagWeight; j++){ // 再遍历背包容量，遍历顺序从小到大，因为每个物品可以选择多次
                dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
            }
        }
        for (int maxValue : dp){
            System.out.println(maxValue + "   ");
        }
    }

### 总结 ###

01背包的核心代码

01背包内嵌的循环是从大到小遍历，为了保证每个物品仅被添加一次。

for(int i = 0; i < weight.size(); i++) { // 遍历物品
        for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
            dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
        }
    }

完全背包的核心代码

完全背包的物品是可以添加多次的，所以要从小到大去遍历。

// 先遍历物品，再遍历背包
    for(int i = 0; i < weight.size(); i++) { // 遍历物品
        for(int j = weight[i]; j <= bagWeight ; j++) { // 遍历背包容量
            dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
    
        }
    }

**注意点：在01背包和完全背包中，当恰好装满背包容量的情形时，需要考虑初始化的情景**

力扣例题1：完全背包，恰好装满背包 [零钱兑换][Link 2]

class Solution {
        public int coinChange(int[] coins, int amount) {
            int[] dp = new int[amount+1];
           for(int j=1;j<=amount;j++){ // 凑成总金额，当物品为0时，初始化为dp[j]为最大无穷数0x3f3f3f3f;
               dp[j] = 0X3f3f3f3f;
           }
            for(int i=0;i<coins.length;i++){
                for(int j = coins[i];j <= amount;j++){
                    dp[j]  = Math.min(dp[j],dp[j-coins[i]]+1);
                }
            }
            return dp[amount] == 0X3f3f3f3f ? -1 : dp[amount];//因为当凑不成总金额时返回-1
        }
    }

力扣例题2：完全背包，恰好装满背包 [零钱兑换II][II]

class Solution {
        public int change(int amount, int[] coins) {
            int[] dp = new int[amount+1];
            dp[0]=1; //注意此处的初始值为当物品为0，背包容量为0时，组合数为1
            for(int i=0;i<coins.length;i++){
                for(int j=coins[i];j<=amount;j++){
                    dp[j] = dp[j]+dp[j-coins[i]];//选择物品组合数：不选中+选中多次的和
                }
            }
            return dp[amount];
        }
    }

力扣例题3：01背包，恰好装满背包 [目标和][Link 3]

class Solution {
       
        public int findTargetSumWays(int[] nums, int target) {
            int sum =0; // 思路：选定一部分数为正数，剩余数为负数，正数+负数=目标值，不添加正负号，2部分数和为sum
            for(int x : nums){
                sum+=x;
            }
            int a  = (target+sum)/2; //只考虑正数部分
            if( a < 0 || (target + sum) % 2 != 0){ // 当不能整除或者考虑数为负数时（因为此处只考虑正数）
                return 0;
            }
            int[] dp = new int[a+1];
            dp[0]=1;   // 注意此处的 初始化，当背包为0时，选择方案为啥都不选
            for(int i=0;i<nums.length;i++){
                for(int j=a;j>=nums[i];j--){
                    dp[j] = dp[j] + dp[j-nums[i]];  //方案数进行累加
                }
            }
            return dp[a];
        }
       
    }

[0185d77fbb7749d4abffe492a45936ca.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/06/f3c12ee9d62e459b971abdfcd44fa9f6.png
[01]: https://programmercarl.com/%E8%83%8C%E5%8C%85%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%8001%E8%83%8C%E5%8C%85-2.html
[Link 1]: https://programmercarl.com/%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80%E5%AE%8C%E5%85%A8%E8%83%8C%E5%8C%85.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
[Link 2]: https://leetcode.cn/problems/coin-change/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj
[II]: https://leetcode.cn/problems/coin-change-ii/description/
[Link 3]: https://leetcode.cn/problems/target-sum/