dp的多种优化方法总结

Posted on | In

二进制优化多重背包

裸的多重背包的复杂度是三次方的，因为在01背包的基础上需要对每种物品按数量逐个增加来测试。事实上大可不必这样，我们可以对于小于这个物品总数的所有二进制位和剩余部分挨个测试，这些测试足够组成原数量范围内的任意一个数，由于二进制位是刚好能表示“选与不选”的，因而也不能用更高进制（例如三进制还要去考虑选择的情况下是选1还是选2，没必要麻烦）。这样一来复杂度会降到nmlog(c)，大部分情况够用。

http://acm.hdu.edu.cn/showproblem.php?pid=2844

给一些面值的钱币，问能表示出几个1到m内的值。直接用多重背包即可，重量和价值相等，最后选dp[i]==i的那些。注意这道题的m可能是负的，所以判断输入要m|n，太阴了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int maxm=1e5+10;
const int maxn=110;

int a[maxn],c[maxn],m,n;
int dp[maxm];
int main(){
    while(scanf("%d%d",&n,&m),m|n){
        for(int i=1;i<=n;i++)
            scanf("%d",a+i);
        for(int i=1;i<=n;i++)
            scanf("%d",c+i);
        memset(dp,0,sizeof(dp));
        int tmp;
        for(int i=1;i<=n;i++){
            int num=1;
            while(num<=c[i]){
                c[i]-=num;
                tmp=num*a[i];
                for(int k=m;k>=tmp;k--){
                    dp[k]=max(dp[k],dp[k-tmp]+tmp);
                }
                num<<=1;
            }
            if(c[i]>0){
                num=c[i];tmp=num*a[i];
                for(int k=m;k>=tmp;k--){
                    dp[k]=max(dp[k],dp[k-tmp]+tmp);
                }
            }
        }

        int ans=0;
        for(int i=1;i<=m;i++)
            if(dp[i]==i)
                ans++;
        printf("%d\n",ans);
    }
    return 0;
}