Vexoben
Jun 15, 2018
题目链接:https://www.lydsy.com/JudgeOnline/problem.php?id=1190
（刷新以获取数学公式）
题意
给你颗宝石，每颗宝石都有重量和价值。要你从这些宝石中选取一些宝石，保证总重量不超过，且总价值最大，并输出最大的总价值。
数据范围:N<=100,W<=2^30
保证每颗宝石的重量符合W=a×2^b(a<=10,b<=30)
题解
题目的限制条件很特殊，一个很自然的想法是根据对宝石进行二进制分组，将问题转化为分组背包。
组内可以进行一次01背包。表示为第组，用了的重量产生的最大价值。
难点在于怎么进行组与组之间的转移。
下设二进制的最高位位。
令表示选了组到第组中的宝石，且剩余重量为的最大价值（也就是中只使用位到第位，且用到第位还留下了的重量），那么考虑转移:
1、显然有，也就是第组什么都不选。
2、枚举第组选什么，于是有。
由于第一种转移的存在，第二维会达到的数量级。但是考虑到，第二维只有当小于的时候更优，所以第二维就只需要保留下的值就可以了。
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=1005;
int n,W,mx;
int w[N],v[N];
LL f[32][N],g[32][N];
void Init() {
mx=0;
for (int i=1;i<=30;i++) if ((W>>i)&1) mx=i;
memset(f,0,sizeof(f));
memset(g,0x80,sizeof(g));
for (int i=1;i<=n;i++) {
scanf("%d%d",&w[i],&v[i]);
int bit=0,num=w[i];
for (int j=1;j<=30;j++) if (w[i]%(1<<j)==0) bit=j,num=w[i]/(1<<j);
for (int j=1000;j>=num;j--) f[bit][j]=max(f[bit][j],f[bit][j-num]+v[i]);
}
}
void Solve() {
Init();
g[mx+1][0]=0;
for (int i=mx+1;i>=0;i--) {
for (int j=0;j<=1000;j++) {
if (g[i][j]<0) continue;
for (int k=1;k<=j;k++) g[i][j-k]=max(g[i][j-k],g[i][j]+f[i][k]);
}
if (!i) continue;
for (int j=0;j<=1000;j++) {
int t=(j<<1)+((W>>(i-1))&1);
if (t>1000) continue;
g[i-1][t]=max(g[i-1][t],g[i][j]);
}
}
LL ans=0;
for (int i=0;i<=1000;i++) ans=max(ans,g[0][i]);
printf("%lld\n",ans);
}
int main() {
while (scanf("%d%d",&n,&W)&&(n+W>0)) Solve();
return 0;
}