动态规划-完全背包问题（纯完全背包、零钱兑换II、组合总数 IV、零钱兑换、完全平方数、单词拆分）、纯多重背包问题_完全背包问题例题和答案

1.完全背包问题（每件物品可放多次）

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

完全背包和01背包问题唯一不同的地方就是，每种物品有无限件。

例子：

背包最大重量为4。

物品为：

每件商品都有无限个！

问背包能背的物品最大价值是多少？

分析：

01背包和完全背包唯一不同就是体现在遍历顺序上，所以下面就不分析动归五步走了，直接针对遍历顺序经行分析！

在前面 01 背包中遍历顺序是这样的

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

01 背包中，里面的遍历层遍历背包容量，从大到小开始遍历，目的是保证每个物品只会被添加一次。

而完全背包中的物品是要被添加多次的，所以这里和01背包的区别就出来了，背包容量要从小到大去遍历。

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

还有一个问题就是，为什么遍历物品在外层循环，遍历背包容量在内层循环

前面在 01 背包中，二维的 dp 数组的两个 for 遍历的先后顺序可以颠倒，一维 dp 数组的两个 for 先后顺序必须是先遍历物品，再去遍历背包（因为这样每一层物品是确定的，一层遍历完后，下一层就可以直接用这层的数据，这也是二维可以压缩为一维的原因）。

而在 完全背包中，对于一维 dp 数组来说，两个 for 循环嵌套顺序是都可以的

因为 dp[j] 是根据下标 j 之前所对应的 dp[j] 计算出来的，只要保证下标 j 之前的 dp[j] 都是经过计算的就可以了

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

代码：

     int[] weight= {1,3,4};
     int[] value= {15,20,30};
     intbagWeight=4;
     
 // 先遍历物品，再遍历背包
 privatestaticvoidtestCompletePack() {
     int[] dp=newint[bagWeight+1];
     for(inti=0; i<weight.length; i++) {
         for(intj=weight[i]; j<=bagWeight; j++) {
             dp[j] =Math.max(dp[j],dp[j-weight[i]] +value[i]);
         }
     }
     // 可以打印看一下
     for (intmaxValue : dp) {
         System.out.println(maxValue+" ");
     }
 }
 ​
 //先遍历背包，再遍历物品
 privatestaticvoidtestCompletePackAnotherWay(){
     int[] dp=newint[bagWeight+1];
     for(inti=1; i<=bagWeight; i++) { // 背包容量
         for(intj=0; j<weight.length; j++) { // 遍历物品
             if(i>=weight[j]) {
                 dp[i] =Math.max(dp[i],dp[i-weight[j]] +value[j]);
             }
         }
     }
     for(intmaxValue : dp) {
         System.out.println(maxValue+" ");
     }
 }

2.零钱兑换 II

题目链接：518. 零钱兑换 II - 力扣（LeetCode）

给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。

请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。

假设每一种面额的硬币有无限个。

题目数据保证结果符合 32 位带符号整数。

示例 1：

输入：amount = 5, coins = [1, 2, 5]输出：4解释：有四种方式可以凑成总金额：5=55=2+2+15=2+1+1+15=1+1+1+1+1

示例 2：

输入：amount = 3, coins = [2]输出：0解释：只用面额 2 的硬币不能凑成总金额 3 。

示例 3：

输入：amount = 10, coins = [10] 输出：1

提示：

• 1 <= coins.length <= 300

• 1 <= coins[i] <= 5000

• coins 中的所有值 互不相同

• 0 <= amount <= 5000

思路：

本道题中，出现了钱币数量不限，并且也给出了背包的容量 amount ，很明显这是一个完全背包的问题。并且纯完全背包是求凑成背包最大价值是多少，而本题是要求凑成总金额的物品组合个数。

比如 1 2 2 ； 2 2 1 是一种组合，两种排列方式，所以要明确题中要求的是组合个数，组合不强调元素之间的顺序，排列强调元素之间的顺序。

下面分析动归五步走

1. 状态定义：dp[j] 表示：凑成总金额为 j 的货币组合数为 dp[j]

2. 状态转移：dp[j] += dp[j - coins[i]]

这个递推公式在前面 目标和 这道题中出现过，都是求装满背包有几种方法。

3. 初始化：dp[0] = 1

这个初始化也是和 目标和 中一样，因为要累加，所以这个初始化一定要为 1

4. 遍历顺序：外层遍历物品，内层遍历背包

本题中的这两个 for 的遍历先后顺序需要理解清楚

如果是纯完全背包的问题，那两个for 遍历的先后顺序没要求，因为纯完全背包求的是装满背包的最大价值是多少，这个和凑成总和的元素有无顺序是没关系的，也就是有顺序可以，无顺序也行，我只关心凑成总和就行，不用管是怎么凑的。

但本题不行，本题是求凑出来的方案数是多少，而方案数就是组合的个数，组合就是元素之间没有明确的顺序（组合 ！= 排列），下面看一下两种的区别。

（1）外层 for 遍历物品（钱币），内层 for 遍历背包（金钱总额）

 for(inti=0; i<coins.length; i++) {
     for(intj=coins[i]; j<=amount; j++) {
         dp[j] +=dp[j-coins[i]];
     }
 }

比如 coins[0] = 1，coins[1] = 5

因为是先遍历的物品，所以是先把 1 加入，再把 5 加入，得到的方法数量只有 {1,5} 这种情况。这种求的就是组合数

（2）外层 for 遍历背包容量，内层 for 遍历物品

 for(int j = 0; j <= amount; j++) {   // 遍历背包容量
     for(int i = 0; i < coins.length; i++) { // 遍历物品
         if(j >= coins[i]) {
             dp[j] += dp[j - coins[i]];
         }
     }
 }

因为是先遍历的背包容量，所以都经过了 1 和 5 的计算，包含了 {1,5} 和 {5，1} 两种情况。这种求的就是排列数

5. 返回值 dp[amount]

代码：

     /** 完全背包问题 
     1. 状态定义：dp[j] 表示：装满容量为 j 的背包有 dp[j] 种方法
     2. 状态转移：dp[j] += dp[j-coins[i]]
     3. 初始化：dp[0] = 1
     4. 遍历顺序：先遍历物品，再遍历背包，从小到大
     5. 返回值：dp[amount]
      */
     publicintchange(intamount, int[] coins) {
         int[] dp=newint[amount+1];
         dp[0] =1;
         for(inti=0; i<coins.length; i++) {
             for(intj=coins[i]; j<=amount; j++) {
                 dp[j] +=dp[j-coins[i]];
             }
         }
         returndp[amount];
     }

3.组合总数 IV

题目链接：377. 组合总和 Ⅳ - 力扣（LeetCode）

给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。

题目数据保证答案符合 32 位整数范围。

示例 1：

输入：nums = [1,2,3], target = 4输出：7解释：所有可能的组合为：(1, 1, 1, 1)(1, 1, 2)(1, 2, 1)(1, 3)(2, 1, 1)(2, 2)(3, 1)请注意，顺序不同的序列被视作不同的组合。

示例 2：

输入：nums = [9], target = 3输出：0

提示：

• 1 <= nums.length <= 200

• 1 <= nums[i] <= 1000

• nums 中的所有元素 互不相同

• 1 <= target <= 1000

进阶：如果给定的数组中含有负数会发生什么？问题会产生何种变化？如果允许负数出现，需要向题目中添加哪些限制条件？

思路：

本道题中说是求组合，但实际上可以看到在示例中又说明顺序不同的序列被视作不同的组合，实际上也就是求排列

组合不强调顺序，(1,5) 和（5,1）是一种组合

排列强调顺序，(1,5) 和（5,1）是两种排列

在上面 零钱兑换 II 这道题中，明确了 组合 和 排列 的做法，其实就是遍历顺序的问题，除了这个基本上和上面一样的

下面写动归五步走、

1. 状态定义：dp[j] 表示：要装满容量为 j 的背包，有 dp[j] 种方法

2. 状态转移：dp[j] += dp[j - nums[i]]

3. 初始化：dp[0] = 1

4. 遍历顺序：

注意本道题求的是 排列，排列是先遍历背包容量，再遍历物品顺序，从小到大

5. 返回值：dp[target]

代码：

     /** 同一物品装多次，完全背包问题，并且题中求的是【排列】个数，
     1. 状态定义：dp[j] :表示装满容量为 j 的背包有 dp[j] 中方法
     2. 状态转移：dp[j] += dp[j - nums[i]]
     3. 初始化：dp[0] = 1
     4. 遍历顺序：先遍历背包，再遍历物品，从小到大
     5. 返回值：dp[target]
      */
     publicintcombinationSum4(int[] nums, inttarget) {
         int[] dp=newint[target+1];
         dp[0] =1;
         for(intj=0; j<=target; j++) {
             for(inti=0; i<nums.length; i++) {
                 if(j>=nums[i]) {
                     dp[j] +=dp[j-nums[i]];
                 }
             }
         }
         returndp[target];
     }

4.零钱兑换

题目链接：322. 零钱兑换 - 力扣（LeetCode）

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

示例 1：

输入：coins = [1, 2, 5], amount = 11输出：3 解释：11 = 5 + 5 + 1

示例 2：

输入：coins = [2], amount = 3输出：-1

示例 3：

输入：coins = [1], amount = 0输出：0

提示：

• 1 <= coins.length <= 12

• 1 <= coins[i] <= 231 - 1

• 0 <= amount <= 104

思路：

在前面 零钱兑换 II 中求的是凑成总金额的物品的组合个数，而本道题是求的凑成这个总金额的钱币最少个数

首先，明确题中说每种硬币的数量是无限的，可以看出完全背包问题，所以

下面分析动归五步走

1. 状态定义：dp[j] 表示：装满容量为 j 的背包，所需钱币的最少个数为 dp[j]

2. 状态转移：dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1)

dp[j] 表示不取当前这个钱币，dp[j - coins[i]] + 1 表示取这个钱币，然后钱币总个数要加1，取这两种情况中最小的

3. 初始化：dp[0] = 0 当要凑的总金额为 0 时，钱币个数一定为 0

其他的下标对应的值，可以分析状态转移方程，dp[j] 必须初始化一个最大的数，否则就会在取 min 时覆盖不了

4. 遍历顺序：先物品后容量（也可以先背包容量后遍历物品），从小到大

5. 返回值：dp[amount]

代码：

 classSolution {
     /** 完全背包问题-每种硬币的数量是无限的
     1. 状态定义：dp[j]:装满容量为 j 的背包，所需最少钱币个数 dp[j]
     2. 状态转移：dp[j] = min(dp[j], dp[j - coins[i]]+1)
     3. 初始化：dp[0] = 0，其他位置根据状态转移方程可以看出，求的都是最小值，所以其他位置初始化都要最大值
     4. 遍历顺序：先物品后容量(也可以先容量后物品)，从小到大
     5. 返回值：dp[amount]
      */
     publicintcoinChange(int[] coins, intamount) {
         int[] dp=newint[amount+1];
         intmax=Integer.MAX_VALUE;
         // 初始化
         for(inti=0; i<dp.length; i++) {
             dp[i] =max;
         }
         dp[0] =0;
         for(inti=0; i<coins.length; i++) {
             for(intj=coins[i]; j<=amount; j++) {
                 // 必须保证 dp[j - coinsp[i]] 的初始值被修改了，否则去 min dp[j] 最大，dp[j - coinsp[i]]也最大，这样就没啥意义
                 if(dp[j-coins[i]] !=max) { 
                     dp[j] =Math.min(dp[j],dp[j-coins[i]]+1);
                 }
             }
         }
         returndp[amount] ==max?-1 : dp[amount];
     }
 }

5.完全平方数

题目链接：279. 完全平方数 - 力扣（LeetCode）

给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

示例 1：

输入：n = 12输出：3 解释：12 = 4 + 4 + 4

示例 2：

输入：n = 13输出：2解释：13 = 4 + 9

提示：

1 <= n <= 104

思路：

虽然题目中要求的是，平方和的，最小数，但实际上对应到完全背包上可以这样说，完全平方数就是物品，并且使用数量也没有限制，整数 n 就是背包最大容量，题目中问的是装满这个背包最小用多少物品

下面分析动归五部走：

1. 状态定义：dp[j] 表示：装满容量为 j 的背包，需要的最少完全平方数的个数为 dp[j]

2. 状态转移：dp[j] = min(dp[j] , dp[j - i*i ] + 1)

3. 初始化：dp[0] = 0

至于其他位置 dp[j] 初始化，因为状态转移方程中每次要取的是最小值，所以其他位置应该初始化为最大值

4. 遍历顺序：因为要求的是最小数，所以先遍历背包或物品都可以

5. 返回值：dp[n]

代码：

     /**
     1. 状态定义：容量为 j 的背包，装满最少需要 dp[j] 个完全平方数
     2. 状态转移：dp[j] = Math.min(dp[j], dp[j - i*i] + 1)
     3. 初始化：dp[0] = 0, 其他位置初始化为最大值
     4. 遍历顺序：先遍历背包容量，后遍历物品（也可以换），从小到大
     5. 返回值：dp[n]
      */
     publicintnumSquares(intn) {
         intmax=Integer.MAX_VALUE;
         int[] dp=newint[n+1];
         for(inti=0; i<=n; i++) {
             dp[i] =max;
         }
         dp[0] =0;
         for(intj=1; j<=n; j++) { // 背包容量
             for(inti=1; i*i<=j; i++) { // 物品
                 // 这里不用再额外判断的原因是，物品是从 1,4,9 .. 开始取的
                     dp[j] =Math.min(dp[j], dp[j-i*i]+1);
             }
         }
         returndp[n];
     }

6.单词拆分

题目链接：139. 单词拆分 - 力扣（LeetCode）

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。

注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

示例 1：

输入: s = "leetcode", wordDict = ["leet", "code"]输出: true解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。

示例 2：

输入: s = "applepenapple", wordDict = ["apple", "pen"]输出: true解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。 注意，你可以重复使用字典中的单词。

示例 3：

输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]输出: false

提示：

• 1 <= s.length <= 300

• 1 <= wordDict.length <= 1000

• 1 <= wordDict[i].length <= 20

• s 和 wordDict[i] 仅有小写英文字母组成

• wordDict 中的所有字符串 互不相同

思路：

这道题也是可以用完全背包的思路来做的， wordDict 中的单词是物品，字符串 s 就是背包，单词能否组成字符串 S，就是问物品能不能把背包装满，并且 wordDict 字典中的单词可以重复使用，这就符合使用完全背包的要求了

下面分析动归五步走：

1. 状态定义：dp[j] 表示：字符串长度为 j ，并且 dp[j] = true,说明可以拆分为一个或多个在字典中出现的单词

2. 状态转移：if ( wordDict.cotains(s.subString(i,j)) && dp[i] = true ) dp[j] = true

如果 [i,j] 这个区间的子串在字典中出现过，并且 dp[i] = true 也就是 i 前面的位置为 ture 的话，那么 dp[j] 就为 true

3. 初始化：dp[0] = true

分析状态转移方程可以得出，dp[j] 的状态是依靠 dp[i] 是否为 ture，所以 dp[0] 就是基础， dp[0] 一定要为 true，否则后面就都为 false

虽然 dp[0] 表示的是字符串为空，这里初始化为 true，表示在字典中有，不符合题意，但实际上题目中给的是一个非空字符串S，所以这里初始化 dp[0] 为 true 只是为了让状态转移方程推导下去

4. 遍历顺序：求排列数，先遍历背包，后遍历物品

经过前面做的这些完全背包的题，可以总结出

如果求组合(无序)数，那就是外层 for 遍历物品，内层 for 遍历背包

如果求排列(有序)数，那就是外层 for 遍历背包，内存 for 遍历物品

而本题要求的就是排列数，比如 s = "applepenapple", wordDict = ["apple", "pen"] ，那么物品的组合必须是 "apple" + "pen" + "apple" 才能组成 "applepenapple"。所以这个是有序的，有序的话就是先遍历背包，后遍历物品

5. 返回值：dp[s.length]

代码：

     /**
     1. 状态定义：字符串长度为 j，并且 dp[j] = true,说明可以拆分为一个或多个在字典中出现的单词
     2. 状态转移：if(wordDict.contains(s.subString(i,j) && dp[i] = true)) 
     {dp[j] = true}
     3. 初始化：dp[0]=true
     4. 遍历顺序：求排列，先背包后物品
     5. 返回值：dp[s.length]
      */
     publicbooleanwordBreak(Strings, List<String>wordDict) {
         HashSet<String>set=newHashSet<>(wordDict);
         boolean[] dp=newboolean[s.length() +1];
         dp[0] =true;
         for(intj=1; j<=s.length(); j++) {// 背包容量
             for(inti=0; i<j; i++) { // 物品
                 if(set.contains(s.substring(i,j)) &&dp[i]) {
                   dp[j] =true;
                 }
             }
         }
         returndp[s.length()];
     }

7.纯多重背包问题

有N种物品和一个容量为V 的背包。第i种物品最多有Mi件可用，每件耗费的空间是Ci ，价值是Wi 。求解将哪些物品装入背包可使这些物品的耗费的空间 总和不超过背包容量，且价值总和最大。

例如：

背包最大重量为10。

物品为：

问背包能背的物品最大价值是多少？

思路：

多重背包和01背包是非常像的， 为什么和 01背包像呢？

每件物品最多有Mi件可用，把Mi件摊开，其实就是一个01背包问题了。

将上面的表格展开就是 01 背包问题了，并且每个物品只用一次

代码：

     // 完全背包
     /**
      * @param weight : 物品重量
      * @param value : 物品价值
      * @param nums : 物品数量
      * @param bagWeight :背包容量
      * @return
      */
     publicstaticinttestMultiPack(List<Integer>weight, List<Integer>value, List<Integer>nums, intbagWeight) {
         // 先将 nums 数组展开，转化为 01 背包问题
         for (inti=0; i<nums.size(); i++) {
             while (nums.get(i) >1) {
                 weight.add(weight.get(i));
                 value.add(value.get(i));
                 nums.set(i,nums.get(i)-1);
             }
         }
         int[] dp=newint[bagWeight+1];
         for (inti=0; i<weight.size(); i++) { // 先遍历物品
             for (intj=bagWeight; j>=weight.get(i); j--) {
                 dp[j] =Math.max(dp[j],dp[j-weight.get(i)] +value.get(i));
             }
         }
         returndp[bagWeight];
     }
 ​
     publicstaticvoidmain(String[] args) {
         List<Integer>weight=newArrayList<>(Arrays.asList(1, 3, 4));
         List<Integer>value=newArrayList<>(Arrays.asList(15, 20, 30));
         List<Integer>nums=newArrayList<>(Arrays.asList(2, 3, 2));
         intbagWeight=10;
         System.out.println(testMultiPack(weight,value,nums,bagWeight));
     }