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;
}