自动搬运

查看原文

来自洛谷，原作者为

	wxwyx **

搬运于2025-08-24 21:42:30，当前版本为作者最后更新于2019-11-09 19:40:59，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

本蒟蒻终于理解了零一背包。( •̀ ω •́ ) 耶

第一次题解。

先配一下我的翻译。

贝茜在逛珠宝店时，买了一个她喜欢的手镯。因此她想从她收集的N（1≤N≤3402）块宝石中选最好的一些镶在手镯上。对于第i块宝石，它的重量为Wi（1≤Wi≤400），并且可以给贝茜增加魅力值Di（1≤Di≤100）。由于贝茜只能忍受重量不超过M（1≤M≤12880）的手镯，她可能无法把所有她喜欢的宝石都镶上。

于是贝茜找到了你，希望你能帮她计算，按照最合理的方案镶宝石，她的魅力值最多能增加多少。

由于每块宝石各不相同，所以典型的零一背包啦。

如果f数组是二维的，肯定是要爆空间的。 （只是本蒟蒻认为其实一维的比较好理解）

话不多说，代码见下。

#include<bits/stdc++.h>
using namespace std;
int w[3410],v[3410];  //w数组存重量，v数组存价值（魅力值）
int f[13000];
int main()
{
	int n,m;   //m是最大重量
	cin>>n>>m;     //与采药输入顺序相反
	for(int i=1;i<=n;i++)
		cin>>w[i]>>v[i];  //输入好像没什么好说的。
	for(int i=1;i<=n;i++)
	{
		for(int j=m;j>=w[i];j--)   //从后向前找不会有其它影响
		{
			f[j]=max(f[j-w[i]]+v[i],f[j]);   //最基本的状态转移方程
		}
	}
	cout<<f[m]<<endl;
	return 0;
}

蒟蒻的第一次题解。管理大大求过