P3188 [HNOI2007]梦幻岛宝珠 做题记录

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

$1\le n \le 100$，$1\le W,w_i,v_i \le 2^{30}$。

保证每个 $w_i$ 能写成 $a \times 2^b\space (a,b \in \mathbb N)$ 的形式，$a \leq 10$ , $b \leq 30$，且答案不超过 $2^{30}$。

不难发现，虽然数据范围很大，但是由于 $w_i=a\times 2^b$，$1\le a\le 10$。所以 $b$ 相同的 $w$ 同时除掉 $2^b$ 之后的和很小，只有 $10n$。那么不难想到按照 $b$ 分组，每组物品单独做背包，最后合并。

那么设 $f_{i,j}$ 表示所有 $b=i$ 的物品，背包容量为 $j\times 2^i$ 时的最大收益。这部分可以在 $O(300n)$ 的时间之内预处理完。

考虑如何合并，设 $tot_i$ 表示 $b=i$ 的物品数量，用类似数位 dp 的思路，设 $g_{i,j}$ 表示前 $i$ 个 $b$，背包容量为 $(m\&((1<<i)-1))+j\times 2^i$（也就是 $m$ 的前 $i-1$ 位加上额外的 $j$ 个 $2^i$）时的最大收益。这样设计状态的好处在于可以处理低位向高位借 $1$ 的情况，那么转移即为

$g_{i,j+k}=\max(g_{i,j+k},f_j+g_{i-1,\min(10\sum\limits_{l=0}^{i-1}tot_l,2k+((m>>(i-1))\&1))})$

即枚举有多少个 $2^i$ 被上一位借了。

这部分的时间复杂度为 $O(3000n)$，总时间复杂度 $O(4000n)$ 左右。

代码如下：

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>

using namespace std;

const int S=105,BS=30,MS=1005;

int n,m;
int tot[BS+5],vw[BS+5][S],vv[BS+5][S];
int f[BS+5][MS],g[BS+5][MS];

void slove()
{
	for(int i=0;i<=BS;i++) tot[i]=false;
	memset(f,0,sizeof(f)),memset(g,0,sizeof(g));
	for(int i=1;i<=n;i++)
	{
		int w,v;
		scanf("%d%d",&w,&v);
		int a=w,b=0;
		while(a&1^1) a>>=1,b++;
//		printf(">> %d %d %d\n",a,b,v);
		vw[b][++tot[b]]=a;
		vv[b][tot[b]]=v;
	}
	for(int i=0;i<=BS;i++)
	{
		for(int j=1;j<=tot[i];j++)
		{
			int w=vw[i][j],v=vv[i][j];
			for(int k=tot[i]*10;k>=w;k--) f[i][k]=max(f[i][k],f[i][k-w]+v);
		}
	}
	// for(int i=0;i<=10;i++)
	// {
		// for(int j=0;j<=20;j++) printf("%d ",f[i][j]);
		// printf("\n");
	// }
	for(int i=0;i<=tot[0]*10;i++) g[0][i]=f[0][i];
	int sm=tot[0];
	for(int i=1;i<=BS;i++)
	{
		sm+=tot[i];
		for(int j=0;j<=sm*10;j++)
		{
			for(int k=0;k<=j;k++)
			{
				g[i][j]=max(g[i][j],f[i][j-k]+g[i-1][min((sm-tot[i])*10,k*2+((m>>i-1)&1))]);
			}
		}
	}
	printf("%d\n",g[BS][m>>BS&1]);
}

int main()
{
	while(1)
	{
		scanf("%d%d",&n,&m);
		if(n==-1&&m==-1) break;
		slove();
	}
	return 0;
}