题意::n个物品,k为倍数。每个物品有两个属性(ai和bi),求在满足所取物品的a属性和是b属性和的k倍的前提下,问a属性的最大值是多少,具体看样例解释,很清楚。
思路:这个题真的是学到了, 对于公式进行变换,然后转化为一部分正数和一部分负数,然后分别求背包,,对于背包,之前一直有一个误区。正确的应该是对于dp[i[代表i体积全部装满所代表的最大价值,因为他可以从背包的转移方程中的出dp[i]=max(dp[i],dp[i-c[i]]+a[i]);这个方程中指出,目前的答案是由减去体积的地方转移来的,而01背包是倒着进行计算,所以的到满体积时的价值
代码:
#include <bits/stdc++.h> using namespace std; const int maxn=105; int n,k,a[maxn],b[maxn],c[maxn],dp[10005],pp[10006]; int main() { while(~scanf("%d%d",&n,&k)){ memset(dp,-0x3f,sizeof(dp)); memset(pp,-0x3f,sizeof(pp)); // memset(c,0,sizeof(c)); dp[0]=pp[0]=0; for(int i=0;i<n;i++){ scanf("%d",&a[i]); } for(int i=0;i<n;i++){ scanf("%d",&b[i]); } for(int i=0;i<n;i++){ c[i]=a[i]-k*b[i]; } for(int i=0;i<n;i++){ if(c[i]>=0){ for(int j=10000;j>=c[i];j--){ dp[j]=max(dp[j],dp[j-c[i]]+a[i]); } } } for(int i=0;i<n;i++){ if(c[i]<0){ c[i]=-c[i]; for(int j=10000;j>=c[i];j--){ pp[j]=max(pp[j],pp[j-c[i]]+a[i]); } } } int ans=-1; for(int i=0;i<=10000;i++){ if(dp[i]==0&&pp[i]==0)continue; else ans=max(ans,dp[i]+pp[i]); } printf("%d\n",ans); } return 0; }