首页 > 代码库 > [NOIP提高组]金明的预算方案
[NOIP提高组]金明的预算方案
题目链接
题目分析
首先这道题目是背包九讲里面第7讲中的有依赖的背包（不过那篇我没怎么看懂），本题中我们可以把附件和主件看成一组，总共有4种情况。
1.选主件 不选附件
2.选主件 选附件1
3.选主件 选附件2
4.选主件 选附件1 和 选附件2
这四种情况，我们可以可以做一次01背包，选出主件这一组中这四种情况中的最大价值即可。
还有一个优化是 因为钱是10的倍数 可以除以10 减少空间占用
#include <cstdio>#include <algorithm>using namespace std;int n,m,V;int v[62],w[62],v1[62],w1[62],v2[62],w2[62];int dp[5005];int ans;int main(){ scanf("%d%d",&V,&m); V/=10; for(int i=1;i<=m;i++){ int x,y,z; scanf("%d%d%d",&x,&y,&z); x/=10; if(z){ if(!v1[z]){ v1[z]=x; w1[z]=x*y; } else{ v2[z]=x; w2[z]=x*y; } } else{ v[i]=x; w[i]=y*x; n=i; } } for(int i=1;i<=n;i++) for(int j=V;j>=v[i];j--){ dp[j] = max(dp[j],dp[j-v[i]]+w[i]); if(j-v[i]-v1[i]>=0) dp[j] = max(dp[j],dp[j-v[i]-v1[i]]+w[i]+w1[i]); if(j-v[i]-v1[i]-v2[i]>=0) dp[j] = max(dp[j],dp[j-v[i]-v1[i]-v2[i]]+w[i]+w1[i]+w2[i]); if(j-v[i]-v2[i]>=0) dp[j] = max(dp[j],dp[j-v[i]-v2[i]]+w[i]+w2[i]); } printf("%d",dp[V]*10); return 0;}
[NOIP提高组]金明的预算方案
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。