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

迈不过友情╰ 2023-09-25 18:30 35阅读 0赞

## **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\] 都是经过计算的就可以了

![2fd22bb516f51a4029c86fc4ee4ee960.png][]

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）][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\]

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

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

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

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

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

本题中的这两个 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\} 两种情况。**这种求的就是排列数**

1.  返回值 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）][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\] 种方法

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

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

1.  遍历顺序：

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

1.  返回值：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）][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\]

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

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

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

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

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

1.  返回值：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）][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\]

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

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

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

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

1.  返回值：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）][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,说明可以拆分为一个或多个在字典中出现的单词

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

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

1.  初始化：dp\[0\] = true

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

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

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

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

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

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

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

1.  返回值：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));
 }

[2fd22bb516f51a4029c86fc4ee4ee960.png]: https://img-blog.csdnimg.cn/img_convert/2fd22bb516f51a4029c86fc4ee4ee960.png
[518. _ II - _LeetCode]: https://leetcode.cn/problems/coin-change-ii/
[377. _ _ - _LeetCode]: https://leetcode.cn/problems/combination-sum-iv/
[322. _ - _LeetCode]: https://leetcode.cn/problems/coin-change/
[279. _ - _LeetCode]: https://leetcode.cn/problems/perfect-squares/
[139. _ - _LeetCode]: https://leetcode.cn/problems/word-break/