01 背包强化练习三题

标签：三题 01 int maxt 背包 maxcnt include dp

## T1

题目：UVA12563

思路：

首先跑一遍『恰好型 01 背包』，这个在我的背包学习笔记中提到了。

memset(dp, -0x3f, sizeof(dp));
dp[0] = 0;

int n, t;
scanf("%d%d", &n, &t);
for (int i = 1; i <= n; i++)
{
	int a;
	scanf("%d", &a);
	for (int j = t; j >= a; j--) dp[j] = max(dp[j], dp[j - a] + 1);
}

输出时遵循：

• \(dp_i\) 尽可能大。

• 在 \(dp_i\) 最大的前提下，\(i\) 最大，这样可以多唱一会。

  不过 \(i \ne t\)，因为至少要留一秒来切换成《劲歌金曲》。

• dp 时并没有计算《劲歌金曲》，所以最后输出时，歌曲数要加 \(1\)，总时间要加 \(678\)。

int maxcnt = 0, maxt = 0;
for (int i = 1; i < t; i++)
	if (dp[i] >= maxcnt)
		maxcnt = dp[i], maxt = i;
printf("Case %d: %d %d\n", num, maxcnt + 1, maxt + 678);

其他细节：

1. 关于 dp 数组的大小

应该开到 \(t\) 的大小，可 \(t \le 10^9\) 咋整？

注意到题目中的一句话：

输入保证所有 \((n+1)\) 首曲子的总长度严格大于 \(t\)。

并且：

每首歌的长度保证不超过 \(3\) 分钟。

这就说明，\(t\) 的实际最大值仅仅是 \(50 \times 180 + 678 = 9678\)。

所以 dp 数组开 \(10000\) 大小就完全足矣。

2. \(t = 1\) 的大坑

计算结果时有这一句代码：

int maxcnt = 0, maxt = 0;

如果你没有初始化成 \(0\) 是绝对不行的。

因为当 \(t = 1\)，for 循环是不会进入的，那么输出时，maxcnt 与 maxt 的初始值将会直接影响结果。

这个应该是很明显的吧，不过我还是被坑了。

整体评价：

这一题相对简单，基本是恰好背包的模板。

代码挺短的。

完整代码：

#include <cstdio>
#include <iostream>
#include <cstring> //给 memset 使用。
using namespace std;
int dp[10005];
void solve(int num)
{
	memset(dp, -0x3f, sizeof(dp));
	dp[0] = 0;
	
	int n, t;
	scanf("%d%d", &n, &t);
	for (int i = 1; i <= n; i++)
	{
		int a;
		scanf("%d", &a);
		for (int j = t; j >= a; j--) dp[j] = max(dp[j], dp[j - a] + 1);
	}
	
	int maxcnt = -1, maxt;
	for (int i = 1; i < t; i++)
		if (dp[i] >= maxcnt)
			maxcnt = dp[i], maxt = i;
	printf("Case %d: %d %d\n", num, maxcnt + 1, maxt + 678);
}
int main()
{
	int T;
	scanf("%d", &T);
	for (int i = 1; i <= T; i++) solve(i);
	return 0;
}

T2

题目：P2340

思路：

看到关键词『选择』与 『和』 就明白可以使用 01 背包。

\(dp_{i, j}\) 中，\(i\) 与正常的 01 背包相同。

\(j\) 表示 \(s_i\) 对应的计算，\(dp_{i, j}\) 表示 \(f_i\) 对应的计算。

此处应为恰好背包，随便跑一次就结束了。

但是！！！这题完全没有这么简单！！！

细节：

1. 数组大小爆炸

dp 数组第一维：\(n\)，即 \(400\)。

第二维：\(\sum_{n}^{i=1}s_i\) 对应的上下界：\(400000 + 400000 = 800000\)。

\(400 \times 800000\) 空间原地爆炸。

解决这一问题，只需使用滚动数组。

发现需要使用的只有 \(i\) 与 \((i-1)\) 两个维度。

所以，将 dp[405][800005] 压成 dp[2][800005]。

那么，原本的状态转移方程：

dp[i][j] = max(dp[i-1][j], dp[i-1][j - s[i]] + f[i]);

压成：

dp[i%2][j] = max(dp[(i-1)%2][j], dp[(i-1)%2][j - s[i]] + f[i]);

即可。

2. 第二维下标负数

\(s_i\) 有可能为负数，则下标可能出现负数并 RE。

这个问题倒也不难解决，最小的负数为 \(-400000\)，所以只需在计算时给下标加上 \(400000\) 来抵消负数即可。

不过输出时需要再减回 \(400000\)。

完整代码：

#include <cstdio>
#include <iostream>
#include <cstring>
#define N 405
#define M 400000
#define MM 800000
using namespace std;
int s[N], f[N], dp[2][MM+5];
int main()
{
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d%d", &s[i], &f[i]);
	
	memset(dp, -0x3f, sizeof(dp));
	dp[0][M] = 0;
	for (int i = 1; i <= n; i++)
	{
		//取这个变量名仅仅是因为想不到好名字了。 
		int monkey = M - i*1000, banana = M + i*1000;
		for (int j = monkey; j <= banana; j++)
			if (0 <= j - s[i] && j - s[i] <= MM)
				dp[i%2][j] = max(dp[(i-1)%2][j], dp[(i-1)%2][j - s[i]] + f[i]);
	}
	int maxn = -1;
	for (int i = M; i <= MM; i++)  //等价于：0-400000 即 s 大于等于 0 
		if (dp[n%2][i] >= 0)  //等价于：f 大于等于 0 
			maxn = max(maxn, i + dp[n%2][i] - M); 
	printf("%d", maxn);
	return 0;
}

注意这行：

int monkey = M - i*1000, banana = M + i*1000;

这是一个细节优化，事实上

int monkey = M, banana = MM;

也是可行的。

你肯定会问：优化了有个屁用啊，就快个常数罢了。

不是的，快了不少呢，无优化（提交记录）接近 3s，优化（提交记录）只有 300ms！

这题到这里就基本琢磨透彻了。

整体评价：

挺难的啊，黄题完全不合理，感觉与 T1 难度调转就合适了。

有很多细节需要考虑。

T3

题目：P1156

思路：

这题貌似与 01 背包的关系不太密切。

首先按 \(t_i\) 从小到大排序。

\(dp_j\) 表示高度为 \(j\) 时，奶牛的最长存活时间。

对于第 \(i\) 个物品，高度为 \(j\) 时，首先得保证 \(dp_j \ge t_i\)，这样才能存活下来。

此时，有两种可能：

• 垫高：\(dp_{j + h_i} = \max\begin{cases}dp_{j + h_i}\\dp_j \end{cases}\)

  并且，如果 \(j + h_i \ge d\)，就可以直接输出当前时间并 return 0。

• 吃掉：\(dp_j = dp_j + f_i\)。

如果等到 \(n\) 个物品都扔完了，程序还没有退出，说明奶牛无法逃脱。

这时，答案即为将全部物品都吃掉的结果，即 \(dp_0\)。

细节：

1. dp 数组初始值

本题不是恰好背包，不需要初始无穷小。

但是，题目中提到：

卡门当前体内有足够持续 \(10\) 小时的能量。

所以初始化 \(dp_0 = 10\)。

2. 计算『堆』与『吃』的顺序

你必须先计算『堆』的结果，再计算 『吃』的结果。

因为 『吃』 的部分会改变 \(dp_j\)，而 『堆』 的结果也需要用到 \(dp_j\)。

所以不得不先算『堆』。

整体评价：

实现并不难，状态转移方程使用了常用的分类法。

此题挺有价值的，可以仔细理解。

完整代码：

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
struct Rubbish
{
	int t, f, h;
}a[105];
bool cmp(Rubbish x, Rubbish y)
{
	return x.t < y.t;
}
int dp[105];
int main()
{
	int d, n; //题目中的 G 用 n 代替。 
	scanf("%d%d", &d, &n);
	for (int i = 1; i <= n; i++) scanf("%d%d%d", &a[i].t, &a[i].f, &a[i].h);
	sort(a+1, a+n+1, cmp);
	dp[0] = 10;
	for (int i = 1; i <= n; i++)
		for (int j = d; j >= 0; j--)
			if (dp[j] >= a[i].t)
			{
				if (j + a[i].h >= d)
				{
					printf("%d", a[i].t);
					return 0;
				}
				dp[j + a[i].h] = max(dp[j + a[i].h], dp[j]);
				dp[j] += a[i].f;
			}
	printf("%d", dp[0]);
	return 0;
}

首发：2022-04-24 19:19:13

标签：三题,01,int,maxt,背包,maxcnt,include,dp
From： https://www.cnblogs.com/liangbowen/p/16622853.html