自动搬运

查看原文

来自洛谷，原作者为

	蓝莲花__ 现在我的QQ名变成Mockingjay了

搬运于2025-08-24 21:55:14，当前版本为作者最后更新于2019-10-01 21:32:52，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

这是一道大水题！？

在做完 开心的金明 和 金明的储蓄计划 后

发现这也是一个简单的背包

在预处理时将每个物品的体积都减去（MINV-1）

其中MINV是所以物品中的最小的体积（价值）

再在dp数组中多加一维，记录一共选了几个

这样做的目的是可以知道当前选的总体积

dp[i][j]表示我选的修改后的物品的体积为i，选了j个

则当前的总体积为：i+j*minv ! ! !

好好理解！！！

代码不长

#include<bits/stdc++.h>
using namespace std;
const int mx=110;
int dp[mx*5][mx],n,w[mx],v[mx],sumv,minv=1e10,sv;
int main()
{
	cin>>n>>sumv;
	for (int i=1;i<=n;i++) cin>>v[i]>>w[i],minv=min(minv,v[i]),sv+=v[i];
	minv--;
        for (int i=1;i<=n;i++) v[i]-=minv;
        sv-=n*minv;
	for (int i=1;i<=n;i++)
	for (int j=sv;j>=v[i];j--)
	for (int k=n;k>=1;k--)
	if (j+k*minv<=sumv) dp[j][k]=max(dp[j][k],dp[j-v[i]][k-1]+w[i]);//cout<<dp[j][k]<<" "<<j<<" "<<k<<endl;
    
	int ans=0;
	for (int j=1;j<=sv;j++)
	for (int i=1;i<=n;i++) ans=max(ans,dp[j][i]);
	cout<<ans;
	return 0;
}