完全背包问题，与01背包比较类似，不过是物体可以被无限重复的选择

1.52. 携带研究材料（第七期模拟笔试）

52. 携带研究材料（第七期模拟笔试）

小明是一位科学家，他需要参加一场重要的国际科学大会，以展示自己的最新研究成果。他需要带一些研究材料，但是他的行李箱空间有限。这些研究材料包括实验设备、文献资料和实验样本等等，它们各自占据不同的重量，并且具有不同的价值。

小明的行李箱所能承担的总重量是有限的，问小明应该如何抉择，才能携带最大价值的研究材料，每种研究材料可以选择无数次，并且可以重复选择。

#include <iostream> #include <vector> using namespace std; int main() { int n, bagWeight; int w, v; cin >> n >> bagWeight; vector<int> weight(n); vector<int> value(n); for (int i = 0; i < n; i++) { cin >> weight[i] >> value[i]; } vector<vector<int>> dp(n, vector<int>(bagWeight + 1, 0)); // 初始化 for (int j = weight[0]; j <= bagWeight; j++) dp[0][j] = dp[0][j - weight[0]] + value[0]; for (int i = 1; i < n; i++) { // 遍历物品 for(int j = 0; j <= bagWeight; j++) { // 遍历背包容量 if (j < weight[i]) dp[i][j] = dp[i - 1][j]; else dp[i][j] = max(dp[i - 1][j], dp[i][j - weight[i]] + value[i]); } } cout << dp[n - 1][bagWeight] << endl; return 0; }

这里是二维dp数组的做法，dp[i][j] 表示从下标为[0-i]的物品，每个物品可以取无限次，放进容量为j的背包，价值总和最大是多少。

• 不放物品i：背包容量为j，里面不放物品i的最大价值是dp[i - 1][j]。

• 放物品i：背包空出物品i的容量后，背包容量为j - weight[i]，dp[i][j - weight[i]] 为背包容量为j - weight[i]且不放物品i的最大价值，那么dp[i][j - weight[i]] + value[i] （物品i的价值），就是背包放物品i得到的最大价值

递推公式：dp[i][j] = max(dp[i - 1][j], dp[i][j - weight[i]] + value[i]);

（注意，完全背包二维dp数组 和 01背包二维dp数组 递推公式的区别，01背包中是dp[i - 1][j - weight[i]] + value[i])）

因为01背包中的物体只有一个，只可以放进去一次，所以物体的范围应该是0到i-1，完全背包中的物体可以被无限次选择，所以选择的范围是0到i

如何初始化，

dp[0][j]，即：存放编号0的物品的时候，各个容量的背包所能存放的最大价值。

那么很明显当j < weight[0]的时候，dp[0][j] 应该是 0，因为背包容量比编号0的物品重量还小。

当j >= weight[0]时，dp[0][j] 如果能放下weight[0]的话，就一直装，每一种物品有无限个。

遍历顺序中，可以外层遍历物体也可以遍历背包容量

#include <iostream> #include <vector> using namespace std; int main() { int N, bagWeight; cin >> N >> bagWeight; vector<int> weight(N, 0); vector<int> value(N, 0); for (int i = 0; i < N; i++) { int w; int v; cin >> w >> v; weight[i] = w; value[i] = v; } vector<int> dp(bagWeight + 1, 0); for(int j = 0; j <= bagWeight; j++) { // 遍历背包容量 for(int i = 0; i < weight.size(); i++) { // 遍历物品 if (j - weight[i] >= 0) dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); } } cout << dp[bagWeight] << endl; return 0; }

这里解法是使用滚动数组，一维的dp做法

dp[i]表示容量为i的背包能够装的最大价值

与01背包的遍历不同，01背包需要先便利物体再反向遍历容量，这里完全背包不需要这样遍历，按照物体或者容量遍历都是可以的。

2.518.零钱兑换II

力扣题目链接(opens new window)

给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。

class Solution { public: int change(int amount, vector<int>& coins) { vector<uint64_t> dp(amount+1,0); dp[0]=1; for(int i=0;i<coins.size();i++){ for(int j=0;j<=amount;j++){ if(j>=coins[i]){ dp[j]+=dp[j-coins[i]]; } } } return dp[amount]; } };

这里也是一种完全背包，不过计算的是组成的金额组合数，并且这里不考虑顺序，所以需要遍历的是物体与容量都可以。

dp[i]表示金额为i能够组成的组合数，所以这里不是求最大值，而是进行相加，不加第i个物体个数加上加第i个物体的个数

3.377. 组合总和 Ⅳ

力扣题目链接(opens new window)

难度：中等

给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数

class Solution { public: int combinationSum4(vector<int>& nums, int target) { vector<uint64_t> dp(target + 1, 0); dp[0] = 1; //与上一题零钱兑换2比较类似，不过零钱兑换是组合问题 //这一题是排列问题，所以字可以先便利背包再遍历物体 //先便利背包的话这样放入背包就有多种顺序 for (int i = 0; i <= target; i++) { // 遍历背包 for (int j = 0; j < nums.size(); j++) { // 遍历物品 if (i - nums[j] >= 0 ) { dp[i] += dp[i - nums[j]]; } } } return dp[target]; } };

与上一题一样，不过这里需要顺序，是排列问题，这样的话遍历顺序就要改变，因为如果说先便利物体的话，物体1只可以出现在物体2的前面，不能在后面，反过来的话就会有多种情况出现。

4.70. 爬楼梯（进阶版）

卡码网：57. 爬楼梯(opens new window)

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬至多m (1 <= m < n)个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

#include<iostream> #include<vector> using namespace std; int main(){ int n,m; cin>>n>>m; vector<int> dp(n+1,0); dp[0]=1; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(i-j>=0){ dp[i]+=dp[i-j]; } } } cout<<dp[n]; return 0; }

同样的这里也是排列的问题，先便利n，表示台阶个数即背包容量，再遍历m表示每次走的台阶数，即选择的物体价值，一共是1到m个物体可以选，每个都可以无限次数的选择。

5.322. 零钱兑换

力扣题目链接(opens new window)

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

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

class Solution { public: int coinChange(vector<int>& coins, int amount) { vector<int> dp(amount + 1, INT_MAX); dp[0] = 0; for (int i = 0; i < coins.size(); i++) { // 遍历物品 for (int j = coins[i]; j <= amount; j++) { // 遍历背包 if (dp[j - coins[i]] != INT_MAX) { // 如果dp[j - coins[i]]是初始值则跳过 dp[j] = min(dp[j - coins[i]] + 1, dp[j]); } } } if (dp[amount] == INT_MAX) return -1; return dp[amount]; } };

不考虑排列的完全背包问题，，dp[i]表示值为i的金额能够组成的种类的最小个数

所以这里的递推公式为取不选择该物体与选择该物体之间的最小值，选择该物体的值为dp[j - coins[i]] + 1

6.279.完全平方数

力扣题目链接(opens new window)

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

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

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

class Solution { public: int numSquares(int n) { //完全平方数是物体，n是背包 vector<int> dp(n + 1, INT_MAX); dp[0] = 0; for (int i = 1; i * i <= n; i++) { // 遍历物品 for (int j = i * i; j <= n; j++) { // 遍历背包 dp[j] = min(dp[j - i * i] + 1, dp[j]); } } return dp[n]; } };

跟上一题一样，都是找最小值，并且都不考虑顺序，dp[i]表示值为i的数，由若干个完全平方组成，组成的个数最少。

7.139.单词拆分

力扣题目链接(opens new window)

给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

说明：

拆分时可以重复使用字典中的单词。

你可以假设字典中没有重复的单词。

class Solution { public: bool wordBreak(string s, vector<string>& wordDict) { unordered_set<string> wordset(wordDict.begin(),wordDict.end()); vector<bool> dp(s.size()+1,false); dp[0]=true; for(int i=1;i<=s.size();i++){ for(int j=0;j<i;j++){ string str=s.substr(j,i-j); if(wordset.find(str)!=wordset.end()&&dp[j]){ dp[i]=true; } } } return dp[s.size()]; } };

用s表示的是背包容量，字典中字符串表示物体，用字典中的字符串装满s

但是这里有限制，这里不仅是需要装满，还需要确定排列的顺序，所以需要先便利背包在遍历物体。

一维dp[i]表示长度为i的字符串使用字典中的字符串是否能被排列成功

这里长度为i的字符串是否能排列成功依赖于dp[j]（j为当前长度去除分割的字符串长度），当dp[j]为true并且j到i之间的字符串也在字典中（表示物体可以被装进背包），那么dp[i]为true。

背包问题总结

1. 确定dp数组（dp table）以及下标的含义
2. 确定递推公式
3. dp数组如何初始化
4. 确定遍历顺序
5. 举例推导dp数组

递推公式存在规律性

问能否能装满背包（或者最多装多少）：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]); ，对应题目如下：

这里装满背包，一般是代表物体的重量与价值是一样的，所以选择装第j个物体或者不装第j个物体之间取最大值，并且选择装第j个物体的时候需要留出的空间就是当前容量减去当前物体（元素）的值。

• 动态规划：416.分割等和子集
• 动态规划：1049.最后一块石头的重量 II

问装满背包有几种方法：dp[j] += dp[j - nums[i]] ，对应题目如下：

装满背包的方法数量，一般是选择装第j个物体与不装第j个物体的个数之和

• 动态规划：494.目标和
• 动态规划：518. 零钱兑换 II
• 动态规划：377.组合总和Ⅳ
• 动态规划：70. 爬楼梯进阶版（完全背包）

问背包装满最大价值：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); ，对应题目如下：

问最大价值，就取选择与不选择之间的最大值

• 动态规划：474.一和零

问装满背包所有物品的最小个数：dp[j] = min(dp[j - coins[i]] + 1, dp[j]); ，对应题目如下：

问最小个数，取选择与不选择之间的最小值，并且选择的时候添加的个数为1.

• 动态规划：322.零钱兑换
• 动态规划：279.完全平方数

遍历顺序也是根据题目的类型来进行选择的

01背包

在动态规划：关于01背包问题，你该了解这些！中我们讲解二维dp数组01背包先遍历物品还是先遍历背包都是可以的，且第二层for循环是从小到大遍历。

和动态规划：关于01背包问题，你该了解这些！（滚动数组）中，我们讲解一维dp数组01背包只能先遍历物品再遍历背包容量，且第二层for循环是从大到小遍历。

一维dp数组的背包在遍历顺序上和二维dp数组实现的01背包其实是有很大差异的，大家需要注意！

完全背包

说完01背包，再看看完全背包。

在动态规划：关于完全背包，你该了解这些！中，讲解了纯完全背包的一维dp数组实现，先遍历物品还是先遍历背包都是可以的，且第二层for循环是从小到大遍历。

但是仅仅是纯完全背包的遍历顺序是这样的，题目稍有变化，两个for循环的先后顺序就不一样了。

如果求组合数就是外层for循环遍历物品，内层for遍历背包。

如果求排列数就是外层for遍历背包，内层for循环遍历物品。

相关题目如下：

• 求组合数：动态规划：518.零钱兑换II
• 求排列数：动态规划：377. 组合总和 Ⅳ (opens new window)、动态规划：70. 爬楼梯进阶版（完全背包）

如果求最小数，那么两层for循环的先后顺序就无所谓了，相关题目如下：

• 求最小数：动态规划：322. 零钱兑换、动态规划：279.完全平方数