自动搬运

查看原文

来自洛谷，原作者为

	Yizhixiaoyun AFOed on 2023/10/21

搬运于2025-08-24 21:44:32，当前版本为作者最后更新于2022-04-12 20:50:00，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题目传送门

前置知识

完全背包

完全背包模板

做法

我们做题的方法考虑完全背包。

找到每个物品的利润，我们发现就是 $r_i - c_i$ ,花费 $c_i$

由此推出状态转移方程：

$dp_j = \max(dp_j,dp_{j-c_i} + r_i - c_i)$

代码

#include<cstdio>
using namespace std;
const int maxn=105;
int n,m,ans,c[maxn],r[maxn],dp[100005];
int max(int a,int b){if(a>b) return a;else return b;}
int main(){
	scanf("%d%d",&n,&m);
	for(register int i=1;i<=n;++i) scanf("%d%d",&c[i],&r[i]);
	for(register int i=1;i<=n;++i){
		for(register int j=c[i];j<=m;++j){
			dp[j]=max(dp[j],dp[j-c[i]]+r[i]-c[i]);
		}
	}
	for(register int i=1;i<=m;++i) ans=max(ans,dp[i]-i+m);
	printf("%d",ans);
}