©2020-2024 ioDraw All rights reserved
<>动态规划——背包问题
对于背包问题，今天我们先讲解，01背包，完全背包，和多重背包。我主要从：
* 什么题可以用背包问题解决
* 背包问题的模板细节，如何准确写出背包。
<>1.什么题可以用背包问题解决
看到题目中有数组，和一个目标值，就要考虑用背包问题解决。
比如：
*
0-1背包中，有v[i]，w[i]两个数组，以及一个最大值（所求结果）。
*
完全背包中，有v[i]，w[i]两个数组,数量不限（其实，换种角度想，完全背包，有多了以为数组，只不过这个数组无限大而已），和一个目标值
*
多重背包中，就是标准的三个数组了w[i],v[i],以及一个目标值
总结一下：有两个数组+求target，就可以考虑用背包问题解决
<>2.背包问题的模板细节，如何准确写出背包。
对于模板，我是以题目来讲解的。
举个栗子
例一
0-1背包问题
有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次
，求解将哪些物品装入背包里物品价值总和最大。
限制条件
* 1 <= n <= 100
* 1 <= wi, vi <= 100
* 1 <= W <= 10000
样例
输入
n = 4
(w, v) = {(2, 3), (1, 2), (3, 4), (2, 2)}
w = 5
输出
7
代码如下
#include <bits/stdc++.h> using namespace std; const int maxl = 105; int n,
w[maxl], v[maxl], dp[maxl][maxl], W; int main(){ cin >> n; for (int i = 0; i <
n; i++){ cin >> w[i] >> v[i]; } cin >> W; memset(dp, 0, sizeof(dp)); for (int i
= 0; i < n; i++) for (int j = 0; j <= W; j++){ if (j < w[i]) dp[i + 1][j] =
dp[i][j]; else dp[i + 1][j] = max(dp[i][j], dp[i][j - w[i]] + v[i]); } cout <<
dp[n][W]; }
* 明确变量，n, v[], w[], dp[] [], W,总的来说除了dp其他题目都要有提到。
* 明白dp意义是什么？一般来说，题目求什么，dp意义就是啥，比如当前题“价值总和最大”。
* for循环的判断条件要不要加等号（有的还加一），这要分类讨论一下，初始从零开始（比如i = 0），就看能不能取得到，能取到就加等于，不能就不加，从0
— n-1（n - 1可取），一共n个物品，所以说n取不到（对于数组v[i], w[i]来说，下标为n就越界了），所以n不加等于。对于W来说，题目中说了
总重量不超过W的物品 ，所以W可以取到，就加上等于。如果下标从1开始，我们每个都加一，保持遍历次数不变（应该没问题把）
* 在循环中的dp，小伙伴们做多了就会发现，有的是和本题相似是dp[i + 1] [j]，但是有的是dp[i + 1] [j + 1]dp[i ] [j
+ 1]等其他形式，不知道怎么写。解决办法就是看循环条件，不加等于的就加一 ，举个栗子，这题的n没有加等于所以我们写成这样dp[i + 1],
W加了等于，所以是dp[j]。连起来就是终结果dp[i + 1] [j]
* 到底输出dp几呢？输出循环条件上的，是n下标就是n，是W下标就是W
* 数量为1，i不相同，要减一（0-1背包），数量无限，i相同（完全背包） dp[i + 1][j] = max(dp[i][j], dp[i][j -
w[i]] + v[i]);//等号后面的i（0-1背包） dp[i + 1][j] = max(dp[i][j], dp[i + 1][j - w[i]]
+ v[i]);//等号后面的i（完全背包）
再来一个栗子练练手(leetcode 1143.最长公共子序列)
例二
最长公共子序列问题
给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，“ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
限制条件
* 1 <= text1.length, text2.length <= 1000
样例
示例 1：
输入：text1 = "abcde", text2 = "ace" 输出：3 解释：最长公共子序列是 "ace" ，它的长度为 3
示例 2：
输入：text1 = "abc", text2 = "abc" 输出：3 解释：最长公共子序列是 "abc" ，它的长度为 3 。
示例 3：
输入：text1 = "abc", text2 = "def" 输出：0 解释：两个字符串没有公共子序列，返回 0 。
代码如下
#include <bits/stdc++.h> using namespace std; const int maxl = 1005; int n, m,
dp[maxl][maxl]; char s1[maxl], s2[maxl]; int main(){ cin >> n >> m; for (int i
= 0; i < n; i++){ cin >> s1[i]; } for (int i = 0; i < m; i++){ cin >> s2[i]; }
memset(dp, 0, sizeof(dp)); for (int i = 0; i < n; i++) for (int j = 0; j < m;
j++){ if (s1[i] == s2[j]) dp[i + 1][j + 1] = dp[i][j] + 1; else dp[i + 1][j +
1] = max(dp[i + 1][j], dp[i][j + 1]); } cout << dp[n][m]; }
步骤分析
* 变量 n, m, dp, s1, s2
* dp意义"两个字符串的最长 公共子序列 的长度"
* 初始化，s1, s2长度都为0时，dp[0] [0] = 0
* 循环条件是否可取，下标从0开始，s1,s2都不可取其n, m
* 输出，由4. 可得dp[n] [m]
* for循环里的递推式，s1[i]与s2[j] 相等，dp[i + 1] [j + 1]就等于，dp[i] [j]最大长度加一，s1[i]与s2[j]
不相等，就记录上一次两个字串的最大长度，这个上一次包含两种情况1.dp[i + 1] [j]2.dp[i] [j + 1]);
接下来讲解完全背包
例三
完全背包问题
有N种物品和一个容量为V的背包，每种物品都有无限件可用。
第i种物品的体积是c，价值是w。求解将哪些物品装入背包可使这些物品的体积总和不超过背包容量，且价值总和最大。
限制条件
* 1 <= n <= 100
* 1 <= wi, vi <= 100
* 1 <= W <= 10000
样例
输入
n = 3
(w, v) = {(3, 4), (4 , 5), (2, 3)}
w = 7
输出
10
代码如下
#include <bits/stdc++.h> using namespace std; const int maxl = 105; int n,
w[maxl], v[maxl], W, dp[maxl][maxl]; int main(){ cin >> n; for (int i = 0; i <
n; i++){ cin >> w[i] >> v[i]; } cin >> W; memset(dp, 0, sizeof(dp)); for (int i
= 0; i < n; i++) for (int j = 0; j <= W; j++){ if (j < w[i]) dp[i + 1][j] =
dp[i][j]; else dp[i + 1][j] = max(dp[i][j], dp[i + 1][j - w[i]] + v[i]); } cout
<< dp[n][W]; }
步骤分析
* 变量 n, dp, v, w, W
* dp意义"价值总和最大"
* 初始化，v, w都为0时，dp[0] [0] = 0,即价值为0
* 循环条件是否可取，下标从0开始，v不可取其n, w可取W
* 输出，由4. 可得dp[n] [m]
* for循环里的递推式，j 表示现在的背包最大重量，w[i],第i个物品重量，如果
现在背包可承受重量小于第i个物品重量，那么价值就是，先前价值，如果装的下w[i],判断是装w[i]价值高，还是不装w[i]价值高
接下来是多重背包
例四
有N种物品和一个容量为W的背包。第i种物品最多有k[i]件可用，每件重量用是w[i]，价值是v[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
限制条件
* 1 <= n <= 100
* 1 <= wi, vi, ki <= 100
* 1 <= W <= 10000
样例
输入
n = 3
(w, v, k) = {(1, 15, 2), (3, 20, 3), (4, 30, 2)}
w = 10
输出
70
代码如下
#include <bits/stdc++.h> using namespace std; const int maxl = 105; int n,
v[maxl], w[maxl], k[maxl], W, dp[maxl][maxl]; int main(){ cin >> n; for (int i
= 0; i < n; i++){ cin >> w[i] >> v[i] >> k[i]; } cin >> W; memset(dp, 0,
sizeof(dp)); for (int i = 0; i < n; i++) for (int j = 0; j <= W; j++){ if (j <
w[i]) dp[i + 1][j] = dp[i][j]; else for (int p = 0; p < k[i] && p * k[i] <= j;
p++) dp[i + 1][j] = max(dp[i][j], dp[i][j - p * w[i]] + p * v[i]); } cout <<
dp[n][W]; }
步骤分析
与前面差不多，这就不多赘述。