给你 颗宝石,每颗宝石都有重量和价值。要你从这些宝石中选取一些宝石,保证总重量不超过 ,且总价值最大,并输出最大的总价值。
,。
保证每个 能写成 的形式, , ,且答案不超过 。
不难发现,虽然数据范围很大,但是由于 ,。所以 相同的 同时除掉 之后的和很小,只有 。那么不难想到按照 分组,每组物品单独做背包,最后合并。
那么设 表示所有 的物品,背包容量为 时的最大收益。这部分可以在 的时间之内预处理完。
考虑如何合并,设 表示 的物品数量,用类似数位 dp 的思路,设 表示前 个 ,背包容量为 (也就是 的前 位加上额外的 个 )时的最大收益。这样设计状态的好处在于可以处理低位向高位借 的情况,那么转移即为
即枚举有多少个 被上一位借了。
这部分的时间复杂度为 ,总时间复杂度 左右。
代码如下:
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
const int S=105,BS=30,MS=1005;
int n,m;
int tot[BS+5],vw[BS+5][S],vv[BS+5][S];
int f[BS+5][MS],g[BS+5][MS];
void slove()
{
for(int i=0;i<=BS;i++) tot[i]=false;
memset(f,0,sizeof(f)),memset(g,0,sizeof(g));
for(int i=1;i<=n;i++)
{
int w,v;
scanf("%d%d",&w,&v);
int a=w,b=0;
while(a&1^1) a>>=1,b++;
// printf(">> %d %d %d\n",a,b,v);
vw[b][++tot[b]]=a;
vv[b][tot[b]]=v;
}
for(int i=0;i<=BS;i++)
{
for(int j=1;j<=tot[i];j++)
{
int w=vw[i][j],v=vv[i][j];
for(int k=tot[i]*10;k>=w;k--) f[i][k]=max(f[i][k],f[i][k-w]+v);
}
}
// for(int i=0;i<=10;i++)
// {
// for(int j=0;j<=20;j++) printf("%d ",f[i][j]);
// printf("\n");
// }
for(int i=0;i<=tot[0]*10;i++) g[0][i]=f[0][i];
int sm=tot[0];
for(int i=1;i<=BS;i++)
{
sm+=tot[i];
for(int j=0;j<=sm*10;j++)
{
for(int k=0;k<=j;k++)
{
g[i][j]=max(g[i][j],f[i][j-k]+g[i-1][min((sm-tot[i])*10,k*2+((m>>i-1)&1))]);
}
}
}
printf("%d\n",g[BS][m>>BS&1]);
}
int main()
{
while(1)
{
scanf("%d%d",&n,&m);
if(n==-1&&m==-1) break;
slove();
}
return 0;
}