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