首页 > 代码库 > 湘潭大学OJ1198Candy(01背包)
湘潭大学OJ1198Candy(01背包)
题目描述
Henry和Lena最近买了很多各种各样的糖…他们决定把所有糖分了… 但是两个人都不希望自己糖的总重量比对方少太多, 鉴于不同的糖的味道不尽相同,所以每个糖都有一个yummy值。 Henry希望知道在两人得到的糖总质量差不大于m的时候,自己的糖yummy值之和的尽量大。
输入
有多组数据 每组数据第一行为两个整数,n,m,(1 <=n <= 100, 0 <= m <= 500) 接下来有两行,每行有n个数,第一行的第i个数表示第i颗糖的重量xi( 0 < xi <= 100), 第二行的第i个数表示第i颗糖的yummy值 yi( 0 < yi <= 100 )
输出
每行输出一组数据的结果, 一个数表示Henry的糖的总yummy值的最大值,如果不存在如题所述的分糖方案,输出-1
样例输入
1 30 43 15 2 290 89 22 76 77
样例输出
-1 153
Source
WCY
#include<stdio.h> int abs(int a) { return a>0?a:-a; } int main() { int n,m,dp[100005],W,w[105],v[105]; while(scanf("%d%d",&n,&m)>0) { W=0; for(int i=0; i<n; i++){ scanf("%d",&w[i]); W+=w[i]; } for(int i=0; i<n; i++) scanf("%d",&v[i]); for(int i=1; i<=W; i++) dp[i]=-1; dp[0]=0; for(int i=0; i<n; i++) for(int tw=W; tw>=w[i]; tw--) if(dp[tw]<dp[tw-w[i]]+v[i]&&dp[tw-w[i]]>=0) dp[tw]=dp[tw-w[i]]+v[i]; int max=-1; for(int tw=W; tw>0; tw--) if(dp[tw]>max&&abs(W-2*tw)<=m) max=dp[tw]; printf("%d\n",max); } }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。