动态规划解决01背包问题
问题来源
假设你是一个聪明的盗贼，你闯入了一家珠宝店。你有一个背包，背包的容量是有限的。珠宝店里有很多宝石，每种宝石的价值和重量都是已知的。你的目标是选择一些宝石放入背包，使得背包中宝石的总价值最大。但是，你不能将宝石分开（也就是说，你不能只拿走一个宝石的一部分），你只能选择拿或者不拿（这就是问题名字中的”01”的来源）。
你作为一个聪明的盗贼,想必你一定知道如何拿取物品获得最大的价值,这道题并不能使用贪心算法(比如优先选择物品价值/重量大的物品),如果使用贪心,则可能导致错误的结果
实际上这个问题可以用动态规划的方法来解决。你可以创建一个二维数组，其中每个元素表示在给定的背包容量和可选宝石的情况下，你可以得到的最大价值。然后，你可以使用这个数组来决定应该拿哪些宝石。
求解方法
记忆化回溯算法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
private:
// memo[i][c] 表示索引为[0...i]的物品，容量为c的背包的最大价值
vector<vector<int>> memo;
// 用 [0...index] 的物品，填充容积为c的背包的最大价值
int bestValue(const vector<int> &w, const vector<int> &v, int index, int c) {
if (index < 0 || c <= 0)
return 0;
if (memo[index][c] != -1)
return memo[index][c];
int res = bestValue(w, v, index - 1, c);
if (c >= w[index])
res = max(res, v[index] + bestValue(w, v, index - 1, c - w[index]));
memo[index][c] = res;
return res;
}
public:
int knapsack01(const vector<int> &w, const vector<int> &v, int C) {
int n = w.size();
memo = vector<vector<int>>(n, vector<int>(C + 1, -1));
return bestValue(w, v, n - 1, C);
}
};
bestValue(w, v, index, c)函数计算的是前index个物品在总容量为c的情况下的最大价值。如果我们已经计算过这个子问题，我们就直接从memo数组中取出结果，否则我们就计算它，并把结果存入memo数组。这样，我们就避免了重复计算相同的子问题，从而提高了算法的效率。
这个解法的时间复杂度是O(nW)，空间复杂度是O(nW)，其中n是物品的数量，W是背包的容量。
二维动态规划
假设我们有3个物品，其重量和价值如下： | 物品 | 重量 | 价值 | |—-|——-|——-| | 1 | 1 | 6 | | 2 | 2 | 10| | 3 | 3 | 12| 背包的最大容量为5。
可以创建一个表格，其中行表示物品，列表示背包的容量。表格中的每个单元格表示在给定的背包容量和可选物品的情况下，我们可以得到的最大价值。 | | 0 | 1 | 2 | 3 | 4 | 5 | |—|—|—|—|—|—|—| | 0 | 0 | 0 | 0 | 0 | 0 | 0 | | 1 | 0 | 6 | 6 | 6 | 6 | 6 | | 2 | 0 | 6 | 10| 16| 16| 16| | 3 | 0 | 6 | 10| 16| 18| 22| 我们从左上角开始填表。对于每个单元格，我们有两种选择：拿当前的物品或者不拿。如果我们拿当前的物品，那么我们就需要在剩余的容量中找到最大的价值。如果我们不拿当前的物品，那么我们就可以在同样的容量下，但是少一个物品的情况中找到最大的价值。我们选择这两种情况中的最大值作为当前单元格的值。
最后，右下角的单元格就是我们的答案，也就是在给定的背包容量和物品的情况下，我们可以得到的最大价值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <vector>
#include <algorithm>
using namespace std;
int knapsack(int W, vector<int>& wt, vector<int>& val, int n) {
vector<vector<int>> K(n + 1, vector<int>(W + 1));
for (int i = 0; i <= n; i++) {
for (int w = 0; w <= W; w++) {
if (i == 0 || w == 0)
K[i][w] = 0;
else if (wt[i - 1] <= w)
K[i][w] = max(val[i - 1] + K[i - 1][w - wt[i - 1]], K[i - 1][w]);
else
K[i][w] = K[i - 1][w];
}
}
return K[n][W];
}
int main() {
vector<int> val = {6, 10, 12};
vector<int> wt = {1, 2, 3};
int W = 5;
int n = val.size();
cout << knapsack(W, wt, val, n) << endl;
return 0;
}
这个解法的时间复杂度是O(nW)，空间复杂度是O(nW)，其中n是物品的数量，W是背包的容量。
一维动态规划(空间优化)
在01背包问题中，我们可以使用一维动态规划进行优化。这种优化主要是减少了空间复杂度，从二维降到了一维。在这种情况下，我们只需要一个一维数组，其中每个元素表示在给定的背包容量下，我们可以得到的最大价值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
int knapsack01(const vector<int> &w, const vector<int> &v, int C) {
int n = w.size();
vector<int> dp(C + 1, 0);
for (int i = 0; i < n; i++)
for (int j = C; j >= w[i]; j--)
dp[j] = max(dp[j], v[i] + dp[j - w[i]]);
return dp[C];
}
};
在这个代码中，我们首先初始化一个长度为背包容量+1的一维数组dp，所有元素都初始化为0。然后，我们遍历每一个物品，对于每一个物品，我们从背包的容量开始，到该物品的重量结束，逆序遍历。对于每一个容量，我们都尝试放入当前的物品，看看是否可以得到更大的价值。如果可以，我们就更新dp[j]的值。最后，dp[C]就是我们的答案，也就是在给定的背包容量和物品的情况下，我们可以得到的最大价值。 时间复杂度O(n),空间复杂度O(n)
完全背包
完全背包问题与01背包问题的主要区别在于，每种物品可以无限次使用，而不是只能使用一次。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
int completeKnapsack(const vector<int> &w, const vector<int> &v, int C) {
int n = w.size();
vector<int> dp(C + 1, 0);
for (int i = 0; i < n; i++)
for (int j = w[i]; j <= C; j++)
dp[j] = max(dp[j], v[i] + dp[j - w[i]]);
return dp[C];
}
};
我们首先初始化一个长度为背包容量+1的一维数组dp，所有元素都初始化为0。然后，我们遍历每一个物品，对于每一个物品，我们从该物品的重量开始，到背包的容量结束，正序遍历。对于每一个容量，我们都尝试放入当前的物品，看看是否可以得到更大的价值。如果可以，我们就更新dp[j]的值。最后，dp[C]就是我们的答案，也就是在给定的背包容量和物品的情况下，我们可以得到的最大价值。
这个解法的时间复杂度是O(n*C)，空间复杂度是O(C)，其中n是物品的数量，C是背包的容量。
分组背包
分组背包问题是背包问题的一个变种，其中物品被分成了若干组，每组中的物品互斥，也就是说在每一组中只能选择一个物品。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
int groupKnapsack(const vector<vector<int>> &w, const vector<vector<int>> &v, int C) {
int n = w.size();
vector<int> dp(C + 1, 0);
for (int i = 0; i < n; i++)
for (int j = C; j >= 0; j--)
for (int k = 0; k < w[i].size(); k++)
if (j >= w[i][k])
dp[j] = max(dp[j], v[i][k] + dp[j - w[i][k]]);
return dp[C];
}
};
我们首先初始化一个长度为背包容量+1的一维数组dp，所有元素都初始化为0。然后，我们遍历每一个组，对于每一个组，我们从背包的容量开始，到0结束，逆序遍历。对于每一个容量，我们都尝试放入当前组的每一个物品，看看是否可以得到更大的价值。如果可以，我们就更新dp[j]的值。最后，dp[C]就是我们的答案，也就是在给定的背包容量和物品的情况下，我们可以得到的最大价值。
这个解法的时间复杂度是O(n*C)，空间复杂度是O(C)，其中n是物品的数量，C是背包的容量。
例题
力扣2915
给你一个下标从 0 开始的整数数组 nums 和一个整数 target 。
返回和为 target 的 nums 子序列中，子序列 长度的最大值 。如果不存在和为 target 的子序列，返回 -1 。
子序列 指的是从原数组中删除一些或者不删除任何元素后，剩余元素保持原来的顺序构成的数组。
示例 1：
输入：nums = [1,2,3,4,5], target = 9 输出：3 解释：总共有 3 个子序列的和为 9 ：[4,5] ，[1,3,5] 和 [2,3,4] 。最长的子序列是 [1,3,5] 和 [2,3,4] 。所以答案为 3 。 示例 2：
输入：nums = [4,1,3,2,1,5], target = 7 输出：4 解释：总共有 5 个子序列的和为 7 ：[4,3] ，[4,1,2] ，[4,2,1] ，[1,1,5] 和 [1,3,2,1] 。最长子序列为 [1,3,2,1] 。所以答案为 4 。 示例 3：
输入：nums = [1,1,5,4,5], target = 3 输出：-1 解释：无法得到和为 3 的子序列。 这个题是一道经典的01背包动态规划问题 初始化一个长度为target+1的动态规划数组dp，所有元素初始化为-1，表示默认情况下无法得到对应的和。dp[0]初始化为0，表示和为0的子序列的长度为0。
遍历输入数组nums，对于每一个数num，从target开始到num结束逆序遍历。对于每一个i，如果dp[i-num]不为-1，说明存在一个和为i-num的子序列，那么加上num就可以得到和为i的子序列，长度为dp[i-num]+1。然后我们用这个长度更新dp[i]。
最后，dp[target]就是我们的答案，也就是和为target的最长子序列的长度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
int lengthOfLongestSubsequence(vector<int>& nums, int target) {
vector<int> dp(target+1,-1);
dp[0]=0;
for(auto &num:nums){
for(int i=target;i>=num;--i){
if(dp[i-num]>=0){
dp[i]=max(dp[i],dp[i-num]+1);
}
}
}
return dp[target];
}
};
这个解法的时间复杂度是O(n*target)，空间复杂度是O(target)，其中n是数组nums的长度，target是目标和。
力扣322
给你一个整数数组 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
这道题是一个经典的完全背包动态规划问题
解法:初始化一个长度为amount+1的动态规划数组dp，所有元素初始化为INT_MAX，表示默认情况下无法得到对应的金额。dp[0]初始化为0，表示金额为0时不需要任何硬币。
遍历从1到amount的每一个金额i，对于每一个金额，再遍历每一种硬币。如果i大于等于当前的硬币面值，并且dp[i-coins[j]]不等于INT_MAX（表示i-coins[j]这个金额是可以得到的），那么我们就可以用dp[i-coins[j]]+1个硬币得到金额i。然后我们用这个硬币数量更新dp[i]。
最后，如果dp[amount]还是INT_MAX，说明没有任何一种硬币组合能组成总金额，返回-1。否则，dp[amount]就是我们的答案，也就是可以凑成总金额所需的最少的硬币个数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
int len=coins.size();
vector<int> dp(amount+1,INT_MAX);
dp[0]=0;
for(int i=1;i<=amount;++i){
for(int j=0;j<len;++j){
if(i-coins[j]>=0&&dp[i-coins[j]]!=INT_MAX){
dp[i]=min(dp[i-coins[j]]+1,dp[i]);
}
}
}
for_each(dp.begin(),dp.end(),[](int &f){cout<<f<<" ";});
if(dp[amount]==INT_MAX) return -1;
return dp[amount];
}
};
这个解法的时间复杂度是O(n*amount)，空间复杂度是O(amount)，其中n是硬币的种类数，amount是目标金额。
力扣1155
这里有 n 个一样的骰子，每个骰子上都有 k 个面，分别标号为 1 到 k 。
给定三个整数 n、k 和 target，请返回投掷骰子的所有可能得到的结果（共有 kn 种方式），使得骰子面朝上的数字总和等于 target。
由于答案可能很大，你需要对 109 + 7 取模。
示例 1：
输入：n = 1, k = 6, target = 3 输出：1 解释：你掷了一个有 6 个面的骰子。 得到总和为 3 的结果的方式只有一种。 示例 2：
输入：n = 2, k = 6, target = 7 输出：6 解释：你掷了两个骰子，每个骰子有 6 个面。 有 6 种方式得到总和为 7 的结果: 1+6, 2+5, 3+4, 4+3, 5+2, 6+1。 示例 3：
输入：n = 30, k = 30, target = 500 输出：222616187 解释：返回的结果必须对 109 + 7 取模。
这道题是需要用到分组背包的思想
初始化一个二维动态规划数组dp，其中dp[i][j]表示使用i个骰子得到总和为j的方式数量。所有元素初始化为0，dp[0][0]初始化为1，表示没有骰子时总和为0的方式只有一种。
遍历从1到n的每一个骰子数量i，对于每一个骰子数量，再遍历从i到target的每一个可能的总和j。对于每一个总和，再遍历从1到k和j中较小的那个的每一个可能的骰子面l。对于每一个骰子面，我们都可以用dp[i-1][j-l]种方式得到总和为j-l，然后再掷出l就可以得到总和为j，所以我们把dp[i-1][j-l]加到dp[i][j]上。
最后，dp[n][target]就是我们的答案，也就是使用n个骰子得到总和为target的方式数量。由于答案可能很大，所以我们在每次更新dp[i][j]的时候都对mod取模。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
long long mod=1000000007;
int numRollsToTarget(int n, int k, int target) {
long long dp[n+1][target+1];
memset(dp,0,sizeof(dp));
dp[0][0]=1;
for(int i=1;i<=n;++i){
for(int j=i;j<=target;++j){
for(int l=1;l<=k&&l<=j;++l){
dp[i][j]=(dp[i][j]+dp[i-1][j-l])%mod;
}
}
}
return dp[n][target];
}
};
这个解法的时间复杂度是O(ntargetk)，空间复杂度是O(n*target)，其中n是骰子的数量，target是目标总和，k是每个骰子的面数。
最后
欢迎关注关注我的LeetCode账号: https://leetcode.cn/u/musing-heisenberg2ed/ 