[学习笔记]背包问题(一)

01背包

有 $N$ 件物品和一个容量为 $V$ 的背包.第 $i$ 件物品体积为 $C_i$ ,价值为 $W_i$ .

求背包最大价值.

$f[i][j]$ 表示前 $i$ 种物品体积为 $j$ 的最大价值,

$f[i][j]=max(f[i-1][j],f[i-1][j-C_i]+W_i)$ .

时间复杂度 $O(VN)$ .

优化空间复杂度

$f[j]$ 表示体积为 $j$ 的最大价值,

$f[j]=max(f[j],f[j-C_i]+W_i)$ (从大到小枚举 $j$ ).

多重背包

有 $N$ 件物品和一个容量为 $V$ 的背包。第 $i$ 种物品最多有 $M_i$ 件可用，体积为 $C_i$ ，价值为 $W_i$ .求背包最大价值.

$f[i][j]$ 表示前 $i$ 种物品体积为 $j$ 的最大价值,

$f[i][j]=max(f[i-1][j-C_i; imes;k]+W_i; imes;k)(0;leq;k;leq;M_i)$

时间复杂度 $O(VMN)$ .

二进制拆分

将 $M_i$ 拆成 $2^0,2^1,2^2...2^k,M_i-$sum_{i=0}^{k}{2^i}$$(sum_{i=0}^{k}{2^i}<M_i;leq;sum_{i=0}^{k+1}{2^i})$$ ,

则在其中任意选取多个数,其和 $$leq$M_i;$

$[1,M_i]$ 间的数都可以通过选取其中多个数得到.

证明:

因为每个十进制数都可拆成二进制数, $2^0,2^1,2^2...2^k$ 分别代表二进制某一位上的 $1$ ,

所以 $[1,$sum_{i=0}^{k}{2^i}$]$ 间的数都可以取到.

加上 $M_i-$sum_{i=0}^{k}{2^i}$$ 后, $[M_i-$sum_{i=0}^{k}{2^i}$+1,M_i]$ 间的数都可以取到.

因为 $M_i;leq;$sum_{i=0}^{k+1}{2^i}$ ,即 $M_i;leq;2^{k+2}-1$ ,

所以 $M_i-2; imes;2^{k+1}+1;leq;0$ ,即 $M_i<2; imes;(2^{k+1}-1)=$2; imes;sum_{i=0}^{k}{2^i}$$ .

所以 $[1,$sum_{i=0}^{k}{2^i}$]cap[M_i-$sum_{i=0}^{k}{2^i}$+1,M_i]=[1,M_i]$ .

例题

Description

设有 $1g,2g,3g,5g,10g,20g$ 的砝码各若干枚（其总重 $leq100000$ ）要求：计算用这些砝码能称出的不同重量的个数，但不包括一个砝码也不用的情况。

Input

一行，包括六个正整数 $a_1,a_2,a_3,a_4,a_5,a_6$ ，表示 $1g$ 砝码有 $a_1$ 个， $2g$ 砝码有 $a_2$ 个... $20g$ 砝码有 $a_6$ 个。相邻两个整数之间用单个空格隔开。

Output

以 $"Total=N"$ 的形式输出，其中 $N$ 为可以称出的不同重量的个数。

Sample Input

1 1 0 0 0 0

Sample Output

Total=3

Solution

多重背包二进制拆分+注意输出格式。

#include<cmath>
#include<ctime>
#include<stack>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define N 105
#define M 100005
using namespace std;
int a[7]={0,1,2,3,5,10,20};
int w[N],n,ans;bool f[N][M];
inline void init(){    
    for(int i=1,s,k;i<=6;++i){
        scanf("%d",&s);k=s;
        for(int j=1;k>=j;j<<=1,k>>=1){
            w[++n]=j*a[i];s-=j;
        }
        if(s) w[++n]=s*a[i];
    }
    f[0][0]=true;
    for(int i=1;i<=n;++i){
        for(int j=0;j<w[i];++j)
            f[i][j]=f[i-1][j];
        for(int j=w[i];j<M;++j)
            f[i][j]=(f[i-1][j]||f[i-1][j-w[i]]);
    }
    for(int j=1;j<M;++j)
        if(f[n][j]) ++ans;
    printf("Total=%d
",ans);
}
int main(){
    freopen("weight.in","r",stdin);
    freopen("weight.out","w",stdout);
    init();
    fclose(stdin);
    fclose(stdout); 
    return 0;
}

单调队列优化

观察式子 $f[i][j]=max(f[i-1][j-C_i; imes;k]+W_i; imes;k)(0;leq;k;leq;M_i)$ ,

每一个 $mod~C_i$ 的值相同的 $j$ 可以用单调队列进行优化.

例题 bzoj1531

完全背包

有 $N$ 件物品和一个容量为 $V$ 的背包.每种物品都有无限件可用,第 $i$ 件物品体积为 $C_i$ ,价值为 $W_i$ .求背包最大价值.

$f[i][j]$ 表示前 $i$ 种物品体积为 $j$ 的最大价值.

$f[i][j]=max(f[i-1][j-C_i; imes;k]+W_i; imes;k)$ .

时间复杂度 $O(N^2V)$

优化时间复杂度

$f[i][j]=max(f[i-1][j],f[i][j-C_i]+W_i)$ .

例题 bzoj1618