自动搬运

查看原文

来自洛谷，原作者为

	yechenguo ด้้้้้็้้้็็็็็้้้้้็็็็็้้้้้้็็็็็้้้้้็็็็็้้้้้้็็็็็้้้้้็็็็็้้้้้้็็็็็้้้้้็็็็็้้้้吼吼吼||支持互关(私)||清团杀关（误杀私）||成功被卡蓝勾线

搬运于2025-08-24 23:03:12，当前版本为作者最后更新于2024-08-29 21:33:25，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

这道题是 01 背包变形。

在看完这道题的时候，思路特别清晰，除了这里的价值和质量是一个东西，这不就是 01 背包变成二维了吗？没什么难度啊？

于是，就有了这段代码。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,a,b,w[2005],dp[2005][2005],maxx;
signed main()
{
	cin>>n>>a>>b;
	for(int i=1;i<=n;i++) cin>>w[i];
	for(int i=1;i<=n;i++)
		for(int j=a;j>=w[i];j--)
			for(int k=b;k>=w[i];k--)
			{
				dp[j][k]=max(dp[j][k],dp[j-w[i]][k]+w[i]);
				dp[j][k]=max(dp[j][k],dp[j][k-w[i]]+w[i]);
				maxx=max(maxx,dp[j][k]);
			}
	cout<<maxx;
	return 0;
}

只有 5 分。

经过一段苦思冥想后，我再次茅塞顿开。这道题的 $j$ 和 $k$ 不能直接到 $w_i$ 就结束了，因为如果这样，那有可能有些下标会更新不到。比如，如果 $w_i$ 没有 $0$ 那么 $dp_{w_i,0}$ 等就会更新不到，会影响结果，所以，$j$ 和 $k$ 要取到 $0$。

最后，上代码！！！

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,a,b,w[2005],dp[2005][2005],maxx;
signed main()
{
	cin>>n>>a>>b;
	for(int i=1;i<=n;i++) cin>>w[i];
	for(int i=1;i<=n;i++)
		for(int j=a;j>=0;j--)
			for(int k=b;k>=0;k--)
			{
				if(j>=w[i]) dp[j][k]=max(dp[j][k],dp[j-w[i]][k]+w[i]);
				if(k>=w[i]) dp[j][k]=max(dp[j][k],dp[j][k-w[i]]+w[i]);
				maxx=max(maxx,dp[j][k]);
			}
	cout<<maxx;
	return 0;
}