来源:自学PHP网 时间:2015-04-14 14:51 作者: 阅读:次
[导读] 把问题重新定义为c=a-b*k;寻找一系列c为0的时候a最大的值。因为c可正可负。所以把c正的01背包一次。把c负的01背包一次。当二者相等的时候,把a相加,取最大值。 includestdio h includestri...
把问题重新定义为c=a-b*k;
寻找一系列c为0的时候a最大的值。
因为c可正可负。
所以把c正的01背包一次。
把c负的01背包一次。
当二者相等的时候,把a相加,取最大值。
#include<stdio.h> #include<string.h> #include<algorithm> #include<iostream> using namespace std; #define INF 99999999 int n,k,i,j; int num[101]; int dp1[100001]; int dp2[100001]; int as[1001]; int bs[1001]; int main() { int a,b; while(~scanf("%d%d",&n,&k)) { for(i=0;i<=100000;i++)dp1[i]=dp2[i]=-INF; dp1[0]=dp2[0]=0; for(i=1;i<=n;i++)scanf("%d",&as[i]); for(j=1;j<=n;j++)scanf("%d",&bs[j]); for(i=1;i<=n;i++) { a=as[i]; b=bs[i]; num[i]=a-b*k; if(num[i]<0) { num[i]=-num[i]; for(j=100000;j>=num[i];j--) { dp2[j]=max(dp2[j],dp2[j-num[i]]+a); } } else { for(j=100000;j>=num[i];j--) { dp1[j]=max(dp1[j],dp1[j-num[i]]+a); } } } int maxn; maxn=-1; for(i=10000;i>=0;i--) { maxn=max(maxn,dp1[i]+dp2[i]); } if(maxn==0)maxn=-1; cout<<maxn<<endl; } return 0; }
|
自学PHP网专注网站建设学习,PHP程序学习,平面设计学习,以及操作系统学习
京ICP备14009008号-1@版权所有www.zixuephp.com
网站声明:本站所有视频,教程都由网友上传,站长收集和分享给大家学习使用,如由牵扯版权问题请联系站长邮箱904561283@qq.com