codevs 1155 金明的预算方案

感谢提供背包九讲的大大orzorz。。。。。

其实把一个牵连背包问题转化成分组背包套（此题不需要）01背包即可。理由，作出的每种策略都是互斥的。

这题我的代码很丑。。。。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
int v,m,w[65],p[65],q[65];
int b[65][3],cnt[65];
int num[65][15],sum=0,cntt[65],cost[65][15];
int f[50005];
int main()
{
memset(cnt,0,sizeof(cnt));
memset(cntt,0,sizeof(cntt));
scanf("%d%d",&v,&m);
for (int i=1;i<=m;i++)
scanf("%d%d%d",&w[i],&p[i],&q[i]);
for (int i=1;i<=m;i++)
{
if (q[i]!=0)
b[q[i]][++cnt[q[i]]]=i;
}
for (int i=1;i<=m;i++)
{
if ((cnt[i]==0) && (q[i]==0))
{
sum++;
num[sum][1]=0;cost[sum][1]=0;
num[sum][2]=w[i]*p[i];cost[sum][2]=w[i];
cntt[sum]=2;
}
else if (cnt[i]==1)
{
sum++;
num[sum][1]=0;cost[sum][1]=0;
num[sum][2]=w[i]*p[i];cost[sum][2]=w[i];
num[sum][3]=w[i]*p[i]+w[b[i][1]]*p[b[i][1]];cost[sum][3]=w[i]+w[b[i][1]];
cntt[sum]=3;
}
else if (cnt[i]==2)
{
sum++;
num[sum][1]=0;cost[sum][1]=0;
num[sum][2]=w[i]*p[i];cost[sum][2]=w[i];
num[sum][3]=w[i]*p[i]+w[b[i][1]]*p[b[i][1]];cost[sum][3]=w[i]+w[b[i][1]];
num[sum][4]=w[i]*p[i]+w[b[i][2]]*p[b[i][2]];cost[sum][4]=w[i]+w[b[i][2]];
num[sum][5]=w[i]*p[i]+w[b[i][1]]*p[b[i][1]]+w[b[i][2]]*p[b[i][2]];cost[sum][5]=w[i]+w[b[i][1]]+w[b[i][2]];
cntt[sum]=5;
}
}
for (int i=1;i<=sum;i++)
for (int k=v;k>=cost[i][2];k--)
for (int j=2;j<=cntt[i];j++)
if (k-cost[i][j]>=0)
f[k]=max(f[k],f[k-cost[i][j]]+num[i][j]);
printf("%d\n",f[v]);
return 0;
}

codevs 1155 金明的预算方案

原文：http://www.cnblogs.com/ziliuziliu/p/5106187.html