题目连接:https://vjudge.net/contest/153156#problem/D
题意:
给出n个物品，有两个属性，问最后第一个属性的总和是第二个属性的k倍的时候，第一个属性最大是多少。
思路:
本来背包做的就不多,这个题让我深度认识了背包
对于这个题由于暴力的情况太多,所以就开始往dp靠拢....我们发现每个物品只有一件,又让求最大值... 很像01背包啊
这个题给了我们条件 要求相除为k,可是都是int,做除法不行,只能想办法转移一下等式 得到a[i]-k*b[i]=0;
那么我们就可以把a[i]看成价值,并把每件物品的a[i]-k*b[i]看成重量,由于这个过程中a[i]-k*b[i]会有负的,所以我们就可以开两个数
组,然后去对正的背一次包,对负的背一次包,我们最后要求的就是背包的容量为0即可, 即枚举两个背包中重量相等的.
注意:
我们需要明白的是,我们那种普通背包,背包不一定要装满, 也就是说背包容量里所有的状态都是可能的,但是我们这个题是必须要
凑出那么多的重量的,否则一些不存在的状态会影响最后的结果.所以我们对dp数组初始化的时候就不能初始化为0,要排除那些不存在的
状态,只去更新那些可能的状态!
#include<bits/stdc++.h> using namespace std; const int maxn=1e4+10; int dp1[111*111]; int dp2[111*111]; int a[111],b[111]; int n,k; struct node { int w; int v; }q[111]; int main() { memset(dp1,-1,sizeof(dp1)); memset(dp2,-1,sizeof(dp2)); cin>>n>>k; dp1[0]=0; dp2[0]=0; for(int i=1;i<=n;i++) { cin>>a[i]; } for(int i=1;i<=n;i++) { cin >>b[i]; q[i].w=a[i]-k*b[i]; q[i].v=a[i]; } for(int i=1;i<=n;i++) { if(q[i].w<0) { q[i].w=-q[i].w; for(int j=maxn;j>=q[i].w;j--) { if(dp1[j-q[i].w]!=-1) dp1[j]=max(dp1[j],dp1[j-q[i].w]+q[i].v); } } else { for(int j=maxn;j>=q[i].w;j--) { if(dp2[j-q[i].w]!=-1)//只要那些可能的状态 dp2[j]=max(dp2[j],dp2[j-q[i].w]+q[i].v); } } } int ans=0; for(int i=0;i<maxn;i++) { if(dp1[i]!=-1&&dp2[i]!=-1) //cout<<i<<" "<<dp1[i]+dp2[i]<<endl; ans=max(dp1[i]+dp2[i],ans); //cout<<i<<endl; } if(ans!=0) printf("%d\n",ans); else printf("-1\n"); return 0; } Marcus-Bao 认证博客专家 推荐系统 ACM算法竞赛 机器学习 本科毕业于国内知名四非大学，现中国科学院大学博士生，中国科学院计算技术研究所vipl实验室，老年ACM铁牌退役选手，喜欢算法竞赛，会点数据结构和算法，熟悉c++，python等；现阶段研究方向主要为机器学习与数据挖掘，比较关注推荐系统，发过顶会，炼过丹，平时博客主要记录些关于算法、数据结构，人工智能技术以及平时看的论文总结分享等，欢迎大家关注我，一起多多交流共同进步！
