动态规划之01背包——三道题助你理解01背包

目录

 二维数组实现

一维数组实现

例一P1164 小A点菜 

P1048 [NOIP 2005 普及组] 采药

P1802 5 倍经验日

---

首先做动规很好的一个办法就是卡哥提出的动规五部曲个人觉得很好用

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

 01 背包
有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

关键就是第i个物品放与不放的区别

从而确定递归顺序

这里大家理解透彻后直接把模板练熟就可以了 

 二维数组实现

#include <bits/stdc++.h>
using namespace std;int main() {int n, bagweight;// bagweight代表行李箱空间cin >> n >> bagweight;vector<int> weight(n, 0); // 存储每件物品所占空间vector<int> value(n, 0);  // 存储每件物品价值for(int i = 0; i < n; ++i) {cin >> weight[i];}for(int j = 0; j < n; ++j) {cin >> value[j];}// dp数组, dp[i][j]代表行李箱空间为j的情况下,从下标为[0, i]的物品里面任意取,能达到的最大价值vector<vector<int>> dp(weight.size(), vector<int>(bagweight + 1, 0));// 初始化, 因为需要用到dp[i - 1]的值// j < weight[0]已在上方被初始化为0// j >= weight[0]的值就初始化为value[0]for (int j = weight[0]; j <= bagweight; j++) {dp[0][j] = value[0];}for(int i = 1; i < weight.size(); i++) { // 遍历科研物品for(int j = 0; j <= bagweight; j++) { // 遍历行李箱容量if (j < weight[i]) dp[i][j] = dp[i - 1][j]; // 如果装不下这个物品,那么就继承dp[i - 1][j]的值else {dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);}}}cout << dp[n - 1][bagweight] << endl;return 0;
}

一维数组实现

// 一维dp数组实现
#include <iostream>
#include <vector>
using namespace std;int main() {// 读取 M 和 Nint M, N;cin >> M >> N;vector<int> costs(M);vector<int> values(M);for (int i = 0; i < M; i++) {cin >> costs[i];}for (int j = 0; j < M; j++) {cin >> values[j];}// 创建一个动态规划数组dp，初始值为0vector<int> dp(N + 1, 0);// 外层循环遍历每个类型的研究材料for (int i = 0; i < M; ++i) {// 内层循环从 N 空间逐渐减少到当前研究材料所占空间for (int j = N; j >= costs[i]; --j) {// 考虑当前研究材料选择和不选择的情况，选择最大值dp[j] = max(dp[j], dp[j - costs[i]] + values[i]);}}// 输出dp[N]，即在给定 N 行李空间可以携带的研究材料最大价值cout << dp[N] << endl;return 0;
}

注：博主比较喜欢直接用一维数组因为比较好用不容易错

例一P1164 小A点菜 

#include <iostream>
using namespace std;
#define N 110
#define M 10002
int n, m;
int a[N];
int dp[M]; // 一维数组int main() {scanf("%d%d", &n, &m);for (int i = 1; i <= n; i++) scanf("%d", &a[i]);dp[0] = 1; // 初始化for (int i = 1; i <= n; i++) {for (int j = m; j >= a[i]; j--) { // 逆序枚举，避免重复计算dp[j] += dp[j - a[i]];}}printf("%d\n", dp[m]);return 0;
}

 博主之前喜欢用二维数组写但真的会稍微麻烦一点

#include <iostream>
using namespace std;
#define N 110
#define  M 10002
int n, m;
int a[N];
int dp[N][M];int main() {scanf("%d%d", &n, &m);for (int i = 1; i <= n; i++) scanf("%d", &a[i]);dp[0][0] = 1;for (int i = 1; i <= n; i++)for (int j = 0; j <= m; j++) {dp[i][j] = dp[i - 1][j];if (j >= a[i]) dp[i][j] += dp[i - 1][j - a[i]];}printf("%d\n", dp[n][m]);return 0;
}

P1048 [NOIP 2005 普及组] 采药

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;int T, M, t[105], w[105], f[1005]; // 使用一维数组int main() {scanf("%d%d", &T, &M);for (int i = 1; i <= M; i++) scanf("%d%d", &t[i], &w[i]);// 初始化memset(f, 0, sizeof(f));for (int i = 1; i <= M; i++) {for (int j = T; j >= t[i]; j--) { // 逆序枚举f[j] = max(f[j], f[j - t[i]] + w[i]);}}printf("%d", f[T]);return 0;
}

不知道有心的小伙伴是否能发现这两个例题都是很典型的01背包问题但为什么会在初始化和递归关系上存在的一定差异，我之前在做的时候也没有太多考虑，看了别人的题解就抄上了，但是回头复习过来还是发现很多问题的

首先这两个题目不同在什么地方呢

点菜的那个题注意要求的是有多少种方法能够凑齐m元

而采药那个题是m时间内采药的最大价值，这个是完成符合01背包的

所以这就导致了初始化的时候大家需要仔细考虑dp代表的意义

以及递推到底是求最值还是累加求数

P1802 5 倍经验日

 

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n, x;
ll dp[100000];
int l[100000], w[100000], u[100000];
int main() {cin >> n >> x;for (int i = 1; i <= n; i++) {cin >> l[i] >> w[i] >> u[i];}for (int i = 1; i <= n; i++) {for (int j = x; j >= 0; j--) {if (j >= u[i]) {dp[j] = max(dp[j] + l[i], dp[j - u[i]] + w[i]);} else {dp[j] += l[i];}}}cout << 5 * dp[x] << endl;return 0;
}

同样也是01背包,但是不同的是这里没有了容量限制，也就是经验值不不是强制要求，这里的经验值是与背包的容量对等的，但是但是，不同的是这里对经验值的要求并不是像背包容量一样，注意看内层循环j 是大于0而不是大于u[i],这是因为题目中给了即使失败也会有经验值。所以在做题的时候一定要根据题目灵活使用模板，而且一定要理解背包的递归逻辑