1. 普通多重背包

把每种物品拆成一个一个的单个的物品,跑01背包。
复杂度:$O(n×m)$(物品数量×背包容量)

2. 多重背包的二进制优化

你把一种物品拆成一个一个的物品累不累啊?
我们知道,用二进制可以表示任何数字,即$2^0,2^1,2^2…$到$2^k$可以表示1到$2×(2^k)-1$内的所有整数。
这就是二进制优化的原理。
我们同样是把某种物品拆开,但我们不一个一个拆。
比如有一类物品数量为$x$,我们把它拆成一组一组的。
第一组有$1$个物品
第二组有$2$个物品
第三组有$4$个物品
第四组有$8$个物品
……
倒数第二组有$2^k$个物品($2^k<x$)
最后一组有$x-2^k$个物品

这一组一组组合起来,一定能表示所有的1到$x$之间的所有数字。

然后我们把每一组看做一个物品。最多有$log2(x)$个物品。

比如$x=10$,我们就把这种物品这样分成4组:$1,2,4,3$
然后不难发现这个东西:

要在这种物品中选的物品数 组合方法
1 1
2 2
3 3
4 4
5 1+4
6 2+4
7 1+2+4
8 1+3+4
9 2+3+4
10 1+2+3+4

组合方法不一定只有这些。
可以证明,这样拆分可以表示所有的要选的物品数。
这样我们就实现了二进制优化了。

具体看代码吧。。。

例题&代码

Coins HDU – 2844
传送门= ̄ω ̄=

题解:
这题就是多重背包的二进制拆分。
状态转移方程:
$f(i)=max(f(i),f(i-a[j])),f(0)=1$
最后输出$f$的总和。
用普通的多重背包会TLE。所以要二进制拆分。

代码:

#include <bits/stdc++.h>
using namespace std;
int n,m,cnt,arr[105],a[100005],ans;
bool book[100005];
int main()
{
    while(scanf("%d%d",&n,&m),n|m)
    {
        memset(book,0,sizeof(book)),book[0]=1,cnt=ans=0;
        for(int i=1;i<=n;i++)scanf("%d",&arr[i]);
        for(int i=1,k,l;i<=n;i++)
        {
            scanf("%d",&k),l=1;
            while(k>l)a[++cnt]=arr[i]*l,k-=l,l<<=1;
            a[++cnt]=arr[i]*k;
        }
        for(int i=1;i<=cnt;i++)
            for(int j=m;j>=a[i];j--)
                if(book[j-a[i]])book[j]=1;
        for(int i=1;i<=m;i++)if(book[i])ans++;
        printf("%d\n",ans);
    }
    return 0;
}

分享至ヾ(≧∇≦*)ゝ:
分类: 所有

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *