点击打开链接
这道题按多重背包做会超时 1e5个物品..
这就要用到二进制优化 如有17个等重等价(W,V)物品 可合成为重(价)分别为 W(V)*1 W(V)*2 W(V)*4 W(V)*8 W(V)*2 的这几个新物品 这样1e5就变为log(1e5) 时间大大优化
这样任意一个1-17范围内的数都可以用这几个二进制系数表示
举个例子 假如背包有15单位的容量 重与价都是3的物品有6个 优化后就是3个分别由1 2 3个物品合成的新物品
打表如下
1th...0 0 0 3 3 3 3 3 3 3 3 3 3 3 3 3
2th...0 0 0 3 3 3 6 6 6 9 9 9 9 9 9 9
3th...0 0 0 3 3 3 6 6 6 9 9 9 12 12 12 15
注意:2th这里放入第二个合成的物品 该物品重量为6 若该物品可以放入背包 则说明这个背包完全可以容纳两个小物品
等于是把放入第二个小物品和放入第三个小物品的过程合并
另外 如果已放物品重量超过了背包容量 背包就不会更新(见表)
而普通背包则是
1th...0 0 0 3 3 3 3 3 3 3 3 3 3 3 3 3***(1th)
2th...0 0 0 3 3 3 6 6 6 6 6 6 6 6 6 6
3th...0 0 0 3 3 3 6 6 6 9 9 9 9 9 9 9***(2th)
4th...0 0 0 3 3 3 6 6 6 9 9 9 12 12 12 12
5th...0 0 0 3 3 3 6 6 6 9 9 9 12 12 12 15
6th...0 0 0 3 3 3 6 6 6 9 9 9 12 12 12 15***(3th)
#include <stdio.h>
int e[11][11];
int pack[100010],w[100010],v[100010];
int main()
{
int bin[18]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072};
int t,n,s,a,b,i,j,k,l,cnt,sum;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&s);
for(i=0;i<=10;i++)
{
for(j=0;j<=10;j++)
{
e[i][j]=0;
}
}
while(n--)
{
scanf("%d%d",&a,&b);
if(a>s) continue;
e[a][b]++;
}
cnt=0;
for(i=1;i<=10;i++)
{
for(j=1;j<=10;j++)
{
if(e[i][j]==0) continue;
for(k=17;k>=0;k--)
{
if(e[i][j]-bin[k]>=0)
{
break;
}
}
for(l=0;l<k;l++)
{
cnt++;
w[cnt]=i*bin[l];
v[cnt]=j*bin[l];
}
cnt++;
w[cnt]=i*(e[i][j]-bin[l]+1);
v[cnt]=j*(e[i][j]-bin[l]+1);
}
}
for(i=0;i<=s;i++)
{
pack[i]=0;
}
for(i=1;i<=cnt;i++)
{
for(j=s;j>=w[i];j--)
{
if(pack[j]<pack[j-w[i]]+v[i])
{
pack[j]=pack[j-w[i]]+v[i];
}
}
}
printf("%d\n",pack[s]);
}
return 0;
}