背包问题 (to be continued)

0x01 01 背包

Problem

有 $N$ 件物品和一个容量为 $V$ 的背包. 第 $i$ 件物品的费用是 $v_i$ , 价值是 $w_i$ .

求 $\max \left{ \left. \sum_{1\leq i\leq N}{w_i\cdot k_i} \right|\sum_{1\leq i\leq N}{v_i\cdot k_i}\leq V,\ k_i\in \left{ 0,1 \right} \right} $

$Solution$

用 $F[i,j]$ 表示 只考虑前 $i$ 个物品 , 体积不超过 $j$ 的物品的最大价值

不难得到状态转移方程为 :

\[F\left[ i,j \right] =\left\{ \begin{array}{l} F\left[ i-1,j \right] ,\,\,\text{if} \,\, v_i>j\\ \max \left\{ F\left[ i-1,j \right] ,F\left[ i-1,j-v_i \right] +w_i \right\} ,\,\,\text{if}\,\,v_i\geq j\\ \end{array} \right. \]

对应的朴素代码为 :

#define rep(i,a,b) for(int i=a;i<=b;i++)

int n, m, v[N], w[N];
int f[N][M];

rep(i,1,n) rep(j,0,m){
    f[i][j]=f[i-1][j];
    if(v[i]<=j) f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);
}

注意到 , 状态转移方程中计算 $F[i,*]$ 时只用到了 $F[i-1,*]$ , 可以考虑用滚动数组将空间复杂度优化到 $O(2V)$

又由于 $j \leq j$ 且 $j-v_i \leq j$ , 第二层循环只需逆序即可. 空间复杂度优化到 $O(V)$

空间复杂度 $O(V)$ 优化代码

#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)

int n, m, v[N], w[N];
int f[M];

rep(i,1,n) per(j,m,v[i])
    f[j]=max(f[j],f[j-v[i]])+w[i];

0x02 完全背包

Problem

有 $N$ 件物品和一个容量为 $V$ 的背包. 第 $i$ 件物品的费用是 $v_i$ , 价值是 $w_i$ .

求 $\max \left{ \left. \sum_{1\leq i\leq N}{w_i\cdot k_i} \right|\sum_{1\leq i\leq N}{v_i\cdot k_i}\leq V \right} $

$Solution$

用 $F[i,j]$ 表示 只考虑前 $i$ 个物品 , 体积不超过 $j$ 的物品的最大价值

不难得到状态转移方程为 :

\[F\left[ i,j \right] =\underset{0\leq k\cdot v_i\leq j}{\max}\left\{ F\left[ i-1,j-k\cdot v_i \right] +k\cdot w_i \right\} \]

对应的朴素代码为 :

#define rep(i,a,b) for(int i=a;i<=b;i++)

int n, m, v[N], w[N];
int f[N][M];

rep(i,1,n) rep(j,0,m)
    for(int k=0;k*v[i]<=j;k++)
        f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);

将原状态转移方程展开 , 观察 :

\[F\left[ i,j \right] =\max \left\{ F\left[ i-1,j \right] ,\ F\left[ i-1,j-v_i \right] +w_i,\ F\left[ i-1,j-2v_i \right] +2w_i,\ \cdots ,\ F\left[ i-1,j-kv_i \right] +kw_i \right\} \]

\[F\left[ i,j-v_i \right] =\max \left\{ F\left[ i-1,j-v_i \right] ,\ F\left[ i-1,j-2v_i \right] +w_i,\ \cdots ,\ F\left[ i-1,j-kv_i \right] +\left( k-1 \right) w_i \right\} \]

可知 :

\[F\left[ i,j \right] =\max \left\{ F\left[ i-1,j \right] ,\ F\left[ i,j-v_i \right] +w_i \right\} \]

可见在计算 $F[i,*]$ 时, 只用到 $F[i-1,*]$ 中的一项 , 以及当前 $F[i,*]$ 已经处理好的部分 , 可以考虑用 正序循环 优化时空复杂度

时间复杂度 $O(NV)$ 空间复杂度 $O(V)$ 优化代码 :

#define rep(i,a,b) for(int i=a;i<=b;i++)

int n, m, v[N], w[N];
int f[M];

rep(i,1,n) rep(j,v[i],m)
    f[j]=max(f[j],f[j-v[i]]+w[i]);

0x03 多重背包

Problem

有 $N$ 件物品和一个容量为 $V$ 的背包. 第 $i$ 件物品的费用是 $v_i$ , 价值是 $w_i$ , 数量为 $s_i$

求 $\max \left{ \left. \sum_{1\leq i\leq n}{w_i\cdot k_i} \right|\sum_{1\leq i\leq n}{v_i\cdot k_i}\leq V,\ 0\leq k_i\leq s_i \right} $

$Solution$

用 $F[i,j]$ 表示 只考虑前 $i$ 个物品 , 体积不超过 $j$ 的物品的最大价值

不难得到状态转移方程为 :

\[F\left[ i,j \right] =\underset{0\leq k\leq s_i}{\underset{0\leq k\cdot v_i\leq j}{\max}}\left\{ F\left[ i-1,j-k\cdot v_i \right] +k\cdot w_i \right\} \]

对应的朴素代码为 :

#define rep(i,a,b) for(int i=a;i<=b;i++)

int n, m, v[N], w[N], s[N];
int f[N][M];

rep(i,1,n) rep(j,0,m)
    for(int k=0;k<=s[i] && k*v[i]<=j;k++)
        f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);

考虑用完全背包的思路进行优化

\[F\left[ i,j \right] =\max \left\{ F\left[ i-1,j \right] ,\ F\left[ i-1,j-v_i \right] +w_i,\ F\left[ i-1,j-2v_i \right] +2w_i,\ \cdots ,\ F\left[ i-1,j-s_iv_i \right] +s_iw_i \right\} \]

\[F\left[ i,j-v_i \right] =\max \left\{ F\left[ i-1,j-v_i \right] ,\,\,\cdots ,\,\,F\left[ i-1,j-s_iv_i \right] +\left( s_i-1 \right) w_i,\ F\left[ i-1,j-\left( s_i+1 \right) v_i \right] +s_iw_i \right\} \]

$F[i,j-v_i]$ 中最后一项 $F[i-1,j-(s_i+1)v_i]+s_iw_i$ 导致无法代换 $F[i,j]$ 中的重复项, 无法直接优化

二进制拆分优化

$\forall 1 \leq i \leq N$ , 注意到 $s_i$ 均可以写成 :

\[s_i=\sum_{i=0}^k{2^i}+c=2^0+2^1+\cdots +2^k+c,\ 0\leq c<2^{k+1} \]

将 $s_i$ 拆分成 $2^0, 2^1, 2^2, \cdots, 2^k, c$ 就可以组合出 $0 \backsim s_i$ 所有数字

Proof

易知, $2^0, 2^1, 2^2, \cdots, 2^k$ 可以组合出 $0\backsim 2^{k+1}-1$ 的所有数字 , 又 $\left[ 0,2^{k+1}-1 \right] +c=\left[ c,2^{k+1}-1 \right] =\left[ c,s_i \right] $ ,

且因为 $0 \le c < 2^{k+1}$ , 所以

\[\left[ 0,2^{k+1}-1 \right] \cup \left[ c,s_i \right] =\left[ 0,s_i \right] \]

$Q.E.D$

将物品拆分后 , 再用 01背包 处理即可.

时间复杂度 $O(NM \log S)$ 优化代码 :

#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)

int n,m,cnt=0/*拆分后数量*/;
int v[N],w[N];
int f[M];

// 二进制拆分
int _v,_w,s;
rep(i,1,n){
    cin>>_v>>_w>>s;
    int k=1;
    while(k<=s){
        cnt++;
        v[cnt]=k*_v, w[cnt]=k*_w;
        s-=k, k<<=1;
    }
    if(s) v[++cnt]=_v*s, w[cnt]=_w*s;
}

// 01 背包
rep(i,1,cnt) per(j,m,v[i])
    f[j]=max(f[j],f[j-v[i]]+w[i]);

0x04 分组背包

Problem

有 $N$ 组物品和一个容量为 $V$ 的背包. 第 $i$ 组一共 $s_i$ 个物品 , 其中第 $j$ 件物品的费用是 $v_{ij}$ , 价值是 $w_{ij}$ .

求 $\max \left{ \left. \sum_{1\leq i\leq N}{\sum_{1\leq j\leq s_i}{w_{ij}\cdot k_{ij}}} \right|\forall 1\leq i\leq N,\ 1\leq j\leq s_i\ \text{s.t.\ }\sum_i{\sum_j{v_{ij}\cdot k_{ij}}}\leq V,\ k_{ij}\in \left{ 0,1 \right} ,\ \sum_j{k_{ij}=1}\ \right} $

$Solution$

用 $F[i,j]$ 表示 只考虑前 $i$ 组物品 , 体积不超过 $j$ 的物品的最大价值

枚举第 $i$ 组物品中每一件物品是否选择 , 不难得到状态转移方程为 :

\[F\left[ i,j \right] =\left\{ \begin{array}{l} \max \left\{ F\left[ i-1,j \right] ,F\left[ i,j \right] \right\} ,\ \text{if\ }v_{ik}>j\\ \max \left\{ F\left[ i-1,j \right] ,F\left[ i-1,j-v_{ik} \right] +w_{ik} \right\} ,\ \text{if\ }v_{ik}\leq j\\ \end{array} \right. ,\ 1\leq k\leq s_i \]

与 01背包 类似 , 可以用倒序循环优化空间复杂度

对应的代码为 :

#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)

int n,m;
int s[N],v[N][S],w[N][S];
int f[M];

rep(i,1,n) per(j,m,0)
    rep(k,1,s[i])
        if(v[i][k]<=j)
            f[j]=max(f[j],f[j-v[i][k]]+w[i][k]);