现在有n(50)个主件,v(100000)体积的背包.每个主件都有一个体积(1000),没有价值.
装了主件后,可以装对应的附件(10),每个附件都有体积(100)和价值(1000000).
求最大价值.
显然是一个依赖背包问题.
我感觉我之前理解错了依赖问题的算法.
所谓对内部附件进行01背包,实际上应该是在原来的dp基础上直接对每个附件进行.
最后与原来的dp基础相比取最大值.注意比较时应该加上主件的元素.
这个题我想的很复杂,做了很长时间然后没有做出来,看了一下题解发现实际上是一个简单题.关键是之前没有掌握到有依赖背包的本质.
WA一次,因为多组数据.
int dp[M],tmp[M];
int n,v;
while(scanf("%d%d",&n,&v)!=EOF)
{
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;i++)
{
int pri_volume=read(),num=read();
memcpy(tmp,dp,sizeof(dp));
while(num--)
{
int volu=read(),valu=read();
for(int j=v;j>=volu;j--)
tmp[j]=max(tmp[j],tmp[j-volu]+valu);
}
for(int j=v;j>=pri_volume;j--)
dp[j]=max(dp[j],tmp[j-pri_volume]);
}
printf("%d\n",dp[v] );
}
学会了这种方法,将金明的预算方案也重做一下.