自动搬运

查看原文

来自洛谷，原作者为

	⚡小林子⚡ 退役垃圾whk人

搬运于2025-08-24 21:27:08，当前版本为作者最后更新于2020-08-30 13:43:59，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

一道考察完全背包的题目。

题目传送门

upd：添加了对完全背包状态转移方程式的详细推导过程。

---

正文

设 $f_{i,j}$ 表示前 $i$ 件物品采药 $j$ 时间能获得的最大价值。

可以列出状态转移方程：

$$f_{i,j}=\max\limits_{k=0}^{k\le \frac{j}{w_i}} (f_{i-1,j-k\times w_i}+k\times v_i) $$

使用二维 dp 显然超时超空间，考虑优化 dp。

把第 $i$ 种草药拆成体积为 $w_i\times 2$ 价值 $v_i\times 2$ 的物品，其中满足 $w_i\times 2\le j$。

• 对于第 $i$ 种草药的出现，我们对第 $i$ 种草药要不要采进行决策。如果不放那么 $f_{i,j}=f_{i-1,j}$；

• 如果确定采，那么应该出现至少一个第 $i$ 种草药，所以当前至少应该出现一个第 $i$ 种草药,即 $f_{i,j}=f_{i,j-w_i}+v_i$。

• $f_{i,j-w_i}$ 里面可能有第 $i$ 种草药，也可能没有第 $i$ 种草药。我们要确保当前至少有一个第 $i$ 个草药，所以要预留 $w_i$ 的空间来存放一个第 $i$ 种草药。

那么完全背包和 01 背包的不同点在哪里呢？

• 从二维数组上区别 01 背包和完全背包也就是状态转移方程就差别在采第 $i$ 种草药时，完全背包在选择采这个草药时，最优解是 $f_{i,j-w_i}+v_i$ 即同行的那一个，而 01 背包比较的是$f_{i-1,j-w_i}+v_i$，上一行的那一个。

时间优化完成了，但是此时空间还是会超，考虑滚动数组。

是否能滚动数组呢？答案当然是可以的。

假设只有一惟 $f_i$，如果是倒序推那么当前 $f_1$ ~ $f_{i-1}$ 都是上一个草药遗留下来的状态，显然不符合要求。

正序推的话 $f_1$ ~ $f_{i-1}$ 均为当前草药已经推过的状态，符合要求。

所以完全背包和 01 背包的区别就在于对时间大小枚举的顺序不同。

具体代码也就好写了：

for(int i=1;i<=n;i++)
	for(int j=w[i];j<=m;j++)
		f[j]=max(f[j],f[j-w[i]]+v[i]);

以上为核心代码。

接下来要注意本题数据范围（有一个坑点）

本题最多有 $10^7$ 时间，每种草药的价值最大是 $10^4$，所以极限情况下价值总和是 $10^7\times 10^4=10^{11}$，会爆 int，所以要开 long long。

十年 OI 一场空，不开 long long 见祖宗。

Code：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e4+5,M=1e7+5;
int n,m,w[N],v[N],f[M];
signed main(){
	scanf("%lld%lld",&m,&n);
	for(int i=1;i<=n;i++)
		scanf("%lld%lld",&w[i],&v[i]);
	for(int i=1;i<=n;i++)
		for(int j=w[i];j<=m;j++)
			f[j]=max(f[j],f[j-w[i]]+v[i]);
	printf("%lld",f[m]);
	return 0;
}

AC！

---

总结

noip 临近，在此提醒大家做题一定要看数据范围，防止因为没开 long long 而遗憾失分。

建议使用 scanf 和 printf，虽然要打的字符多一些，但是时间更快（或者您使用 ios::sync_with_stdio(0) 也可以），防止考场上因为输入输出而 TLE。

$\sf{The\,End.}$