noip2006 金明的预算方案 (有依赖的背包转化为01背包)
P1313金明的预算方案
Accepted
描述金明今天很开心,家里购置的新房就要领钥匙了,新房里有一间金明自己专用的很宽敞的房间。更让他高兴的是,妈妈昨天对他说:“你的房间需要购买哪些物品,怎么布置,你说了算,只要不超过N元钱就行”。今天一早,金明就开始做预算了,他把想买的物品分为两类:主件与附件,附件是从属于某个主件的,下表就是一些主件与附件的例子: 设第j件物品的价格为v[j],重要度为w[j],共选中了k件物品,编号依次为j1,j2,……,jk,则所求的总和为:v[j1]*w[j1]+v[j2]*w[j2]+ …+v[jk]*w[jk]。(其中*为乘号)请你帮助金明设计一个满足要求的购物单。 格式输入格式输入文件的第1行,为两个正整数,用一个空格隔开: 输出格式输出文件只有一个正整数,为不超过总钱数的物品的价格与重要度乘积的总和的最大值 样例1样例输入1[复制]
1000 5 800 2 0 400 5 1 300 5 1 400 3 0 500 2 0 样例输出1[复制]
2200 限制1s 来源NOIP2006第二题 解析:由于每个主件只有0、1或者2件附件,一共只有四种情况:1主,1主1附(2),1主两附。我们直接将这4种情况处理出来,然后对于每个体积v,只使用这四种情况中的一种。 代码: #include<cstdio> #include<algorithm> using namespace std; const int max_n=3200; const int max_m=60; int n,m,s[max_m]; int v[max_m+20][4],w[max_m+20][4]; int f[max_n+20]; int main() { int i,j,k,a,b,c; scanf("%d%d",&n,&m),n/=10; for(i=1;i<=m;i++) { scanf("%d%d%d",&a,&b,&c); if(c==0)k=s[i],w[i][k]=a*b,v[i][k]=a/10,s[i]++; else k=s[c],w[c][k]=a*b,v[c][k]=a/10,s[c]++; } for(i=1;i<=m;i++) { if(s[i]==3) { s[i]++; v[i][3]=v[i][1]+v[i][2]+v[i][0]; w[i][3]=w[i][1]+w[i][2]+w[i][0]; } if(s[i]>=2)v[i][1]+=v[i][0],w[i][1]+=w[i][0]; if(s[i]>=3)v[i][2]+=v[i][0],w[i][2]+=w[i][0]; } for(i=1;i<=m;i++) for(k=n;k>=1;k--) for(j=0;j<s[i];j++)if(k>=v[i][j]) f[k]=max(f[k],f[k-v[i][j]]+w[i][j]); printf("%dn",f[n]); return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |