Description：

$N$ 个物品，每个物品都有重量和价值。选一些物品总重量不超过 $W$ 且总价值最大。

$N\leqslant100,W\leqslant2^{30},$ 并且保证每个物品的重量符合 $a\times2^b$ 。

Solution：

既然告诉 $w[i]=a\times2^b$ 那就按二进制位考虑，设 $f_1[i][j]$ 表示只考虑 $b=i$ 的物品 $a$ 的和为 $j$ 所能获得的最大价值，这个可以把物品按 $b$ 分组然后每组做 $01$ 背包，再设 $f_2[i][j]$ 表示所有 $b<i$ 的物品都已考虑完，都合并到 $i$ 这一位上需要的容积为 $j\times 2^i$ 能获得的最大价值，转移时发现 $f_2[i-1][j]$ 等价于 $f_2[i][\lceil\frac{j-(m的第i位是1)}2\rceil]$ ，可以把每个 $f_2[i][j]$ 都像这样提高一位，看成一个物品，然后在 $f_1[i][j]$ 的基础上再做一个类似分组背包的东西，因为只能选一个 $f_2$ ，否则会选重，但是由于有重量为 $0$ 的物品存在所以需要用一个 $g[i]$ 辅助转移。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<vector>

#include<cctype>

#include<cstring>

using namespace std;

int n,m;

#define R register

inline int rd()

{

	R int res = 0,f = 1;

	R char c = getchar();

	while(!isdigit(c))

	{

		if(c == '-')f = -1;

		c = getchar();

	}

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res * f;

}

#define MAXN 110

int w[MAXN],v[MAXN];

struct item{int w,v;};

vector<item> s[32];

#define MAX 1000

int f[32][MAX + 10];

int g[MAX + 10]; 

int main()

{

	while(scanf("%d%d",&n,&m) && n != -1 && m != -1)

	{

		for(R int i = 0;i <= 31;++i)s[i].clear();

		for(R int i = 1;i <= n;++i)

		{

			w[i] = rd();v[i] = rd();

		}

		for(R int i = 1;i <= n;++i)

		{

			R int cnt = 0;

			while(w[i] % 2 == 0)

			{

				++cnt;

				w[i] /= 2;

			}

			s[cnt].push_back((item){w[i],v[i]});

		}

		memset(f,0xc0,sizeof(f));

		for(R int i = 0;i <= 31;++i)

		{

			f[i][0] = 0;

			for(R vector<item>::iterator it = s[i].begin();it != s[i].end();++it)

			{

				for(R int j = MAX;j >= it -> w;--j)

				{

					f[i][j] = max(f[i][j],f[i][j - it -> w] + it -> v);

				}

			}

		}

		for(R int i = 0;i <= 30;++i)

		{

			memset(g,0xc0,sizeof(g));

			for(R int k = MAX;k >= 0;--k)

			{

				for(R int j = 0;j <= MAX;++j)

				{

					R int vi = (j - ((m >> i) & 1) + 1) / 2;

					if(k >= vi)g[k] = max(g[k],f[i + 1][k - vi] + f[i][j]);

					else break;

				}

			}

			for(R int k = MAX;k >= 0;--k)f[i + 1][k] = g[k];

		}

		cout << f[31][0] << endl;

	}

	return 0;

}