在华为秋招的笔试题中，出了两道背包问题，分值分别为100和200，而总分是600。我用暴力递归的方法只拿到了55%和30%，并直接导致分值为300的第三题没有时间完成。而我甚至没有意识到自己是在暴力求解！
综述
背包问题是一类经典的动态规划问题。动态规划问题的自底向上解法和带备忘的自顶向下解法时间复杂度是一样的，但由于没有递归的开销，自底向上方式通常具有更小的系数。
主要参考文章：https://zhuanlan.zhihu.com/p/93857890。我所写的代码只是达到了AC的要求，没有进一步优化时间效率，空间也未优化。
经典背包问题
01背包
一共有N件物品，第i件物品的重量为w[i]，价值为v[i]。背包承载重量上限为W，求背包能装入的物品的最大价值是多少？
动态规划就是面临“选”或者“不选”的问题，用递归去分析没错，但如果采用不带备忘的递归去实现，最坏情况下时间复杂度将达到O(N^2)。如果物品的重量相对背包的承载上限比较小，那实际运行就会接近这个最坏复杂度。下面采用自底向上的方式求解该问题。
定义dp[i][j]表示：将前i件物品放进限重为j的背包中可以获得的最大价值。这个状态，或者说最优解dp[i][j]，可以分下面两种情形：
- 如果最优解中不含第i件物品，则dp[i][j]=dp[i-1][j]
- 如果最优解中含有第i件物品，则dp[i][j]=dp[i-1][j-w[i]]+v[i]
采用循环来实现，时间复杂度为O(NV)。
下面是OJ上的真题，比直接求最大价值复杂一点点。代码AC了，但没有优化空间复杂度。
https://vjudge.net/problem/SCU-4580#author=0
#include <bits/stdc++.h>using namespace std;int main() {int T;cin >> T;while (T-- > 0) {int N, V;cin >> N >> V;vector<int> weight(N + 1);vector<int> volume(N + 1);for (int i = 1; i <= N; ++i) {cin >> weight[i];}for (int i = 1; i <= N; ++i) {cin >> volume[i];}vector<vector<int>> dp(N+1, vector<int>(V+1, 0));vector<vector<int>> v(N+1, vector<int>(V+1, 0));for (int i = 1; i <= N; ++i) {for (int j = 1; j <= V; ++j) {if (volume[i] > j) {dp[i][j] = dp[i-1][j];v[i][j] = v[i-1][j];} else {int tmp = dp[i-1][j-volume[i]] + weight[i];if (tmp > dp[i-1][j]) {dp[i][j] = tmp;v[i][j] = v[i-1][j-volume[i]] + volume[i];} else {dp[i][j] = dp[i-1][j];v[i][j] = v[i-1][j];}}}}cout << dp[N][V] << ' ' << v[N][V] << endl;}}
完全背包
https://vjudge.net/problem/51Nod-2649
完全背包问题与01背包问题唯一的不同就是物品的数量变成了“无限多个”。此时状态变量的定义可以保持不变，但是需要修改状态转移方程，时间复杂度仍然为O(NV)
int main() { int N, V; cin >> N >> V;
vector<int> volume(N+1);
vector<int> value(N+1);
for (int i = 1; i <= N; ++i) {
cin >> volume[i] >> value[i];
}
vector<vector<int>> dp(N+1, vector<int>(V+1, 0));
for (int i = 1; i <= N; ++i) {
for (int j = 1; j <= V; ++j) {
if (j < volume[i]) {
dp[i][j] = dp[i-1][j];
} else {
dp[i][j] = max(dp[i-1][j], dp[i][j-volume[i]] + value[i]);
}
}
}
cout << dp[N][V] << endl;
}
<a name="MHnuG"></a>
#### 多重背包
[https://www.acwing.com/problem/content/4/](https://www.acwing.com/problem/content/4/)<br />相对于完全背包，多重背包限制每种物品的数量为有限多个。依然用dp[i][j]表示在限重为j的背包中装入前i种物品所能获得的最大价值。此时状态dp[i][j]不再只由两种情况转移而来。
- 如果最优解不包含第i种物品，则dp[i][j]=dp[i-1][j]
- 如果最优解包含第i种物品1件，则dp[i][j]=dp[i-1][j-w[i]] + v[i]
- ……
- 如果最优解包含第i种物品amount[i]件，则dp[i][j]=dp[i-1][j-w[i]*amount[i]] + v[i]*amount[i]
最坏情况下的时间复杂度为O(N*totalAmount)。
```cpp
#include <bits/stdc++.h>
using namespace std;
int main() {
int N, V;
cin >> N >> V;
vector<int> volume(N + 1);
vector<int> value(N + 1);
vector<int> amount(N + 1);
for (int i = 1; i <= N; ++i) {
cin >> volume[i] >> value[i] >> amount[i];
}
int dp[N+1][V+1];
memset(dp, 0, sizeof(dp));
for (int i = 1; i <= N; ++i) {
for (int j = 1; j <= V; ++j) {
if (j < volume[i]) {
dp[i][j] = dp[i-1][j];
} else {
dp[i][j] = dp[i-1][j];
for (int k = 1; k <= amount[i]; ++k) {
if (j < k*volume[i]) {
break;
}
int tmp = dp[i-1][j - k*volume[i]] + k*value[i];
if (tmp > dp[i][j]) {
dp[i][j] = tmp;
}
}
}
}
}
cout << dp[N][V] << endl;
}
其它情况
能否恰好装满?
https://leetcode-cn.com/problems/partition-equal-subset-sum/ 分割等和子集。
dp[i][j]表示前i个元素能否选出和为j的集合，状态转移方程为（注意方程中数组下标i从1开始，代码中则是从0开始的）：
- 如果j<nums[i]，dp[i][j]=dp[i-1][j]
- 否则，如果j==nums[i]，dp[i][j]=true
否则，dp[i][j]= dp[i-1][j] || dp[i-1][j-nums[i]]
bool canPartition(vector<int>& nums) { int cnt = 0; for (auto e : nums) { cnt += e; } if (cnt % 2 != 0) { return false; } int target = cnt / 2; int sz = nums.size(); bool dp[sz+1][target+1]; memset(dp, 0, sizeof(dp)); for (int i = 1; i <= sz; ++i) { for (int j = 1; j <= target; ++j) { if (j < nums[i-1]) { dp[i][j] = dp[i-1][j]; continue; } if (j == nums[i-1]) { dp[i][j] = true; } else { dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i-1]]; } } } return dp[sz][target]; }能否用最少的物品恰好装满？
https://leetcode-cn.com/problems/coin-change/ 零钱兑换。
状态转移类似完全背包，直接见代码。int coinChange(vector<int>& coins, int amount) { if (amount == 0) { return 0; } int sz = coins.size(); int MAX = 10001; vector<vector<int>> dp(sz+1, vector<int>(amount+1, MAX)); for (int i = 1; i <= sz; ++i) { for (int j = 1; j <= amount; ++j) { if (coins[i-1] > j) { dp[i][j] = dp[i-1][j]; } else if (coins[i-1] == j) { dp[i][j] = 1; } else { dp[i][j] = min(dp[i-1][j], dp[i][j-coins[i-1]] + 1); } } } return dp[sz][amount] < MAX ? dp[sz][amount] : -1; }恰好装满的方案有多少种？
https://leetcode-cn.com/problems/target-sum/ 目标和。这一题比一般的方案数背包问题要复杂。
本题的状态转移不难，但由于下标不存在负数，所以对数组下表的转换要格外注意！int findTargetSumWays(vector<int>& nums, int S) { int sz = nums.size(); int sum = 0; for (auto e : nums) { sum += e; } int UP_LIMIT = sum; // >= 0 int DOWN_LIMIT = -1 * sum; if (S > UP_LIMIT || S < DOWN_LIMIT) { return 0; } int dp[sz+1][2*sum + 1]; memset(dp, 0, sizeof(dp)); dp[0][sum] = 1; for (int i = 1; i <= sz; ++i) { for (int j = DOWN_LIMIT + sum; j <= UP_LIMIT + sum; ++j) { if (j - nums[i-1] <= UP_LIMIT + sum && j - nums[i-1] >= DOWN_LIMIT + sum) { dp[i][j] += dp[i-1][j - nums[i-1]]; } if (j + nums[i-1] <= UP_LIMIT + sum && j + nums[i-1] >= DOWN_LIMIT + sum) { dp[i][j] += dp[i-1][j + nums[i-1]]; } } } return dp[sz][S + sum]; }二维背包
https://leetcode-cn.com/problems/ones-and-zeroes/
注意在该情景中，若j和k不全为0，状态值并不为0！int findMaxForm(vector<string>& strs, int m, int n) { int sz = strs.size(); vector<int> cnt_zero(sz + 1, 0); vector<int> cnt_one(sz + 1, 0); for (int i = 1; i <= sz; ++i) { for (auto ch : strs[i-1]) { if (ch == '0') { ++cnt_zero[i]; } else { ++cnt_one[i]; } } } int dp[sz+1][m+1][n+1]; memset(dp, 0, sizeof(dp)); for (int i = 1; i <= sz; ++i) { for (int j = 0; j <= m; ++j) { for (int k = 0; k <= n; ++k) { if (cnt_zero[i] > j || cnt_one[i] > k) { dp[i][j][k] = dp[i-1][j][k]; } else { dp[i][j][k] = max(dp[i-1][j][k], dp[i-1][j-cnt_zero[i]][k-cnt_one[i]] + 1); } } } } return dp[sz][m][n]; }
若有收获，就点个赞吧
0 人点赞
