天天看点

ycb的ACM进阶之路 QDU

点击打开链接

这道题按多重背包做会超时 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;
}