代码随想录刷题|完全背包理论基础 LeetCode 518. 零钱兑换II 377. 组合总和 Ⅳ

目录

完全背包理论基础

518. 零钱兑换||

思路

零钱兑换||

377. 组合总和 Ⅳ

思路

组合总和IV

完全背包理论基础

• 完全背包问题和01背包问题的区别
  • 完全背包问题：
    • 有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品都有无限个（也就是可以放入背包多次），求解将哪些物品装入背包里物品价值总和最大
  • 01背包问题：
    • 有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大
  • 完全背包和01背包问题唯一不同的地方就只啊，完全背包中每一物品都有无限件
• 完全背包的解法：
  • 01背包中的物品只能用一次
  • 只要将01背包中物品使用无限次就是完全背包
  • 在之前01背包的一维dp数组中，为了避免物品被重复使用，在遍历背包的时候采用的是倒序遍历

    • for (int i = 0; i < weight.length; i++) {   // 物品
          for (int j = bagSize; j >= weight[i]; j-- ) { // 背包
              dp[j] = Math.max(dp[j],dp[j-weight[i]]+value[i]);
          }
      }
      

  • 所以，只要将遍历背包的顺序改成正序遍历，那么物品就可以被重复多次添加了，那么就是完全背包的使用了

    • for (int i = 0; i < weight.length; i++) {   // 物品
          for (int j = weight[i]; j <= bagSize ; j++ ) { // 背包
              dp[j] = Math.max(dp[j],dp[j-weight[i]]+value[i]);
          }
      }
      

• 完全背包的遍历顺序：
  • 不同于01背包的一维dp数组，完全背包的时候背包的遍历和物品的遍历是可以交换的
  • 遍历方式一：先物品再背包

    • for (int i = 0; i < weight.length; i++) {   // 物品
          for (int j = weight[i]; j <= bagSize ; j++ ) { // 背包
              dp[j] = Math.max(dp[j],dp[j-weight[i]]+value[i]);
          }
      }
      

  • 遍历方式二：先背包再物品

    • for (int j = 1; j <= bagSize ; j++ ) { // 背包
          for (int i = 0; i < weight.length; i++) {   // 物品
              if ( j - weight[i] >= 0) {
                  dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
              }
          }
      }
      

  • 因为dp[j]是根据下标 j 之前所对应的 dp[j]计算出来的，只要保证下标 j 之前的dp[j]都是经过计算的就可以了
• 最终代码
  • 遍历方式一：先遍历物品再遍历背包

  • public class BagProblem2 {
        public static void main(String[] args) {
            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[] dp = new int[bagSize + 1];
     
            // 初始化dp数组
            // 将dp[]数组初始化为0，默认就是，不用操作
     
            // 遍历填充dp数组
            // 外层循环代表几个物品，循环几次
            // 内层循环更换最大值
     
            for (int i = 0; i < weight.length; i++){ // 遍历物品
                for (int j = weight[i]; j <= bagSize; j++){ // 遍历背包容量
                    dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
                }
            
     
                // 打印dp数组
                for (int num : dp) {
                    System.out.print(num + "\t");
                }
                System.out.print("\n");
            }
     
     
     
        }
    }
    

  • 遍历方式二：先遍历背包，再遍历物品

  • public class BagProblem2 {
        public static void main(String[] args) {
            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[] dp = new int[bagSize + 1];
     
            // 初始化dp数组
            // 将dp[]数组初始化为0，默认就是，不用操作
     
            // 遍历填充dp数组
            // 外层循环代表背包容量
            // 内层循环代表物品
            for (int j = 1; j <= bagSize ; j++ ) { // 背包
                for (int i = 0; i < weight.length; i++) {   // 物品
                    if ( j - weight[i] >= 0) {
                        dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
                    }
                }
                
                // 打印dp数组
                for (int num : dp) {
                    System.out.print(num + "\t");
                }
                System.out.print("\n");
            }
        }
    }
    

518. 零钱兑换||

题目链接：力扣

思路

        这道题目可以算是 纯完全背包问题 和 目标和 的结合体

        总的来说就是当物品可以无限使用的时候，装满背包有多少种方法

        初始化和递推公式跟 目标和 一样
        遍历方式和 纯的完全背包问题 一样，但是背包的遍历和物品的遍历不能替换顺序，因为纯完全背包理论求的是填满背包的最大物品重量，而这道题目求得是有多少种方法

        遍历顺序很重要：
                如果求组合数，就是外层for循环遍历物品，内层for循环遍历背包
                如果求排列数，就是外层for循环遍历背包，内层for循环遍历物品

零钱兑换||

class Solution {
    public int change(int amount, int[] coins) {
 
        // 创建dp数组
        int[] dp = new int[amount + 1];
 
        // 初始化
        dp[0] = 1;
 
        // 填充数组
        for (int i = 0; i < coins.length; i++) {
            for (int j = coins[i]; j <= amount; j++) {
                dp[j] += dp[j-coins[i]];
            }
        }
 
        return dp[amount];
    }
}

377. 组合总和 Ⅳ

题目链接：力扣

思路

        正常的思路是使用回溯算法，但是这道题目使用回溯算法会超时，所以需要使用动态规划。但是动态规划只能求这个排列数是多少，不能求组合种具体的元素

        这道题目使用动态规划就是在上面所说的 如果求排列数，就是外层for循环遍历背包，内层for循环遍历物品

        只需要改变遍历的顺序，先对背包进行遍历，再对物品进行遍历就可以

组合总和IV

class Solution {
    public int combinationSum4(int[] nums, int target) {
 
        // 创建dp数组
        int[] dp = new int[target + 1];
 
        // 初始化dp数组
        dp[0] = 1;
 
        // 填充dp数组
        // 与组合数的遍历顺序相反,先遍历背包，再遍历物品
        for (int j = 1; j <= target; j++) {
            for (int i = 0; i < nums.length; i++) {
                if (j - nums[i] >= 0) {
                    dp[j] += dp[j - nums[i]];
                }
            }
        }
 
        return dp[target];
    }
}