[文章目录]
Description
给你N颗宝石，每颗宝石都有重量和价值。要你从这些宝石中选取一些宝石，保证总重量不超过W，且总价值最大为，并输出最大的总价值。数据范围：N<=100;W<=2^30,并且保证每颗宝石的重量符合a*2^b（a<=10;b<=30）
一个数据范围超大的背包？？？
GXZ讲这道提的时候说应该发现一些特点。显然是重量。假设对于不同的b分别跑背包的话，剩余体积不超过n*a。那么问题就在于处理不同的b之间的问题上了。当一位剩b体积的收益，可以转化为下一位剩b*2加上总体积在次微商的只。那么就可以从高位向低位递推了。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m,ans,f[1100],g[1100];
struct node
{
int a,b,w;
}a[110];
bool cmp(node x,node y){return x.b>y.b;}
int main()
{
while(~scanf("%d%d",&n,&m))
{
if(n==-1) return 0;
int i,j,k,tmp;
for(i=1;i<=n;++i)
{
scanf("%d%d",&a[i].a,&a[i].w);
for(a[i].b=0;a[i].b<=30&&!((a[i].a>>a[i].b)&1);a[i].b++);
a[i].a>>=a[i].b;
}
sort(a+1,a+n+1,cmp);
memset(f,0xc0,sizeof f); f[0]=0;
for(i=30,j=1;~i;--i)
{
memset(g,0xc0,sizeof g);
for(k=0;k<=1000;++k)
tmp=min(1000,(k<<1)+((m>>i)&1)),
g[tmp]=max(g[tmp],f[k]);
swap(g,f);
for(;j<=n&&a[j].b==i;++j)
for(k=a[j].a;k<=1000;++k)
f[k-a[j].a]=max(f[k-a[j].a],f[k]+a[j].w);
}
for(ans=i=0;i<=1000;++i) ans=max(ans,f[i]);
printf("%d\n",ans);
}
return 0;
}