题意

给定 \(n\) 颗宝石，每颗宝石都有重量和价值。要你从这些宝石中选取一些宝石，保证总重量不超过 \(W\)，且总价值最大，并输出最大的总价值。

数据范围

\(1 \leq n \leq 100,1 \leq W,w_i,v_i,\leq 2^{30}\)。

保证每个 \(w_i\) 能写成 \(a \times 2^b\space (a,b \in \mathbb N)\)
的形式，\(a \leq 10\)，\(b \leq 30\)

思路

初看本题就是一个 01 背包的模板题，但是 \(W \leq 2^{30}\) 决定了不能直接用朴素的 \(O(nW)\) 方法做。

注意到 \(w_i\) 满足一个性质：\(a \times 2^b\space (a,b \in \mathbb N),a \leq 10,b \leq 30\)。其实每个十进制数都可以表示成 \(a \times 2^b\) 的形式（例如 \(114514=114514 \times 2^0\)）。因为十进制数和二进制数一一对应。所以本题的关键点在于 \(a \leq 10\)。这决定了可以考虑将所有的物品按照 \(b\) 的大小分组。每个物品的体积就可以转化为 \(a\)，这样就可以节省大量的空间和时间。

设 \(g[i][j]\) 表示在 \(b=i\) 这一组中选取 \(j\) 体积物品的最大价值。显然，只需要在每一组内部做一次 01 背包即可。

然而，\(W\) 并不满足 \(w_i\) 的性质，这就决定了只有 \(g\) 数组并不能得到答案。

需要另外再开一个 \(f\) 数组转移答案。

考虑 \(f\) 的状态如何设计。显然根据 \(w_i\) 的性质，需要有一个维度 \(i\) 来表示目前枚举到 \(b=i\) 这一组 \(w\)，还需要另外一个维度 \(j\) 表示在这一组中选取了体积为 \(j\) 的物品。同时要保证体积不能超过 \(W\)。怎么实现呢？假设当前已经填到了 \(W\) 在二进制表示下的最高位 \(k\) 那一组，显然输出答案时，\(i=1\)。那么就要保证后面位数上填的数不超过 \(W-2^k=W \And (1<<(k-1))\)。分析到这里，状态就很很清楚了。

设 \(f[i][j]\) 表示在 \(0 \sim i\) 组一共选取了 \(2^j+W \And (1<<(i-1))\) 的原始体积的最小花费。

显然，状态转移方程不可能只是简单的

\(f[i][j]=\max(f[i-1][j-k]+g[i][k])\)。

\(k\) 表示在第 \(i\) 组选取体积为 \(w\) 的物品（这一句的体积都指分组后的体积），注意到在第 \(i\) 组选取体积为 \(j-k\) 的物品，就等价于在第 \(i-1\) 组选取体积为 \((j-k)*2\) 的物品。根据设计的状态，\(j*2^i\) 的原始体积(下面都指原始体积)就由 \(k*2^i\) 和 \(2*(j-k)*2^{i-1}\) 贡献。根据状态，还需要 \(2^{W>>(i-1) \And1}\) 的体积去贡献 \(W \And (1<<(i-1))\)。于是就可以得到状态转移方程：

\(f[i][j]=\max(f[i-1][(j-k)*2+(W>>(i-1) \And 1)]+g[i][k])\)。

最后，本题要多测，别忘了清空数组。

code：

#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
const int N=50;
const int M=5020;
#define int long long
int g[N][M],S,f[N][M],n,W;
vector<int>v[N],w[N];
int max(int a,int b){return a>b?a:b;}
void init()
{
	S=0;
	for(int i=0;i<N;i++) v[i].clear(),w[i].clear();
	memset(f,0,sizeof(f));
	memset(g,0,sizeof(g));
}
signed main()
{
//	freopen("233.in","r",stdin);
	while(scanf("%lld%lld",&n,&W))
	{
		if(n==-1&&W==-1) break;
		init();
		for(int tw,tv,i=1;i<=n;i++)
		{
			scanf("%lld%lld",&tw,&tv);
			int ws=0;
			while(((tw>>ws)&1)==0) ws++;
//			printf("%lld %lld\n",ws,tw>>ws);
			v[ws].push_back(tv);
			w[ws].push_back(tw>>ws);
		}
		while((W>>S)) S++;
		for(int i=0;i<S;i++)
		{
			if(w[i].size()==0) continue;
			for(int j=0;j<w[i].size();j++)
				for(int k=520;k>=w[i][j];k--)
					g[i][k]=max(g[i][k],g[i][k-w[i][j]]+v[i][j]);
		} 
		for(int i=0;i<S;i++)
		    for(int j=520;j>=0;j--)
		        for(int k=0;k<=j;k++)
		            f[i][j]=max(f[i][j],g[i][k]+f[i-1][(j-k)*2+((W>>(i-1))&1)]);
		printf("%lld\n",f[S-1][1]);
	}
	return 0;
}