动态规划 第3讲 背包九讲

本章基于《背包九讲》展开
背包问题是线性DP中一类重要而特殊的模型。背包问题，不是线性DP的全部，更不是DP的全部
注意，优化的过程，需要认真思考，认识其本质
本章需要细细琢磨，慢慢理解，深刻理解

0/1背包问题

例题，01背包问题(含优化)

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int f[N][N];
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= m; j++)
        {
            f[i][j] = f[i - 1][j];  // 右边集合为空，不包含i
            if (j >= v[i]) f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
        }
    cout << f[n][m] << endl;
    return 0;
}

// 滚动数组优化，f[N][M] -> f[2][M]
#include <iostream>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int f[2][N];   
//计算f[i]这一层，只用到了f[i-1]这一层的数据，用滚动数组
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];
    f[0][0] = 0;
    for (int i= 1; i <= n; i++)
        for (int j = 0; j <= m; j++)
        {
            f[i & 1][j] = f[(i - 1) & 1][j];
            if (j >= v[i]) f[i & 1][j] = max(f[i & 1][j], f[(i - 1) & 1][j - v[i]] + w[i]);
        }
    cout << f[n & 1][m] << endl;
    return 0;
}

// 二维优化到一维
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int f[N];   
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];
    for (int i = 1; i <= n; i++)
        for (int j = m; j >= v[i]; j--)
        {
            f[j] = max(f[j], f[j - v[i]] + w[i]);
            //这与我们的刚才的二维里的状态计算不一致，刚才实际应该是f[i - 1][j - v[i]]
            //若j从大到小枚举，算f[j]的时候，f[j - v[i]]还没有被更新过，存的就是f[i - 1][j - v[i]]
            //这样就和二维的状态转移方程等价了
        }
    cout << f[m] << endl;
    return 0;
}

// define ZerOnePack
#include <iostream>
using namespace std;
const int N = 1010;
int n, m;
int f[N];
int v[N], w[N];
void zeroonepack(int f[], int vi, int wi)
{
    for (int j = m; j >= vi; j--)
        f[j] = max(f[j], f[j - vi] + wi);
}
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];
    for (int i = 1; i <= n; i++)
        zeroonepack(f, v[i], w[i]);
    cout << f[m] << endl;
    return 0;
}

初始化的细节问题

完全背包问题

例题，完全背包问题(含优化)

// 3 loops
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int f[N][N];
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];
    /*
    for 物品 枚举阶段
        for 体积 枚举状态
            for 决策 枚举决策
    */
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= m; j++)
            for (int k = 0; k *v[i] <= j; k++)
                f[i][j] = max(f[i][j], f[i - 1][j - v[i] * k] + w[i] * k);
    cout << f[n][m] << endl;
    return 0;
}

// 根据以上对转移方程的数学分析
// 3 loops -> 2 loops，减少了一层k循环
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int f[N][N];
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= m; j++)
        {
            f[i][j] = f[i - 1][j];
            if (j >= v[i]) f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]);
        }
    cout << f[n][m] << endl;
    return 0;
}

# 二维变成一维
求f[j]的时候，f[j–v[i]]已经被算过了， 
f[j-vi]是第i层的 f[j-vi] 和状态转移方程一致

// f[i][j] -> f[j]
// 二维变一维
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int f[N];
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];
    for (int i = 1; i <= n; i++)
        for (int j = v[i]; j <= m; j++)
            f[j] = max(f[j], f[j - v[i]] + w[i]);
    cout << f[m] << endl;
    return 0;
}

想清楚： 一维的写法，为什么只差了从大到小循环 和 从小大到循环

// define completepack
#include <iostream>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int f[N];
void completepack(int f[], int vi, int wi)
{
    for (int j = vi; j <= m; j++)
        f[j] = max(f[j], f[j - vi] + wi);
}
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];
    for (int i = 1; i <= n; i++)
        completepack(f, v[i], w[i]);
    cout << f[m] << endl;
    return 0;
}

多重背包问题

例题，多重背包问题 I

// 多重背包问题 I
// 0 < N,V ≤ 100
// 0 < vi,wi,si ≤ 100
// 3 loops
// O(n^3)
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 110;
int n, m;
int v[N], w[N], s[N];
int f[N][N];
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> v[i] >> w[i] >> s[i];
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= m; j++)
            for (int k = 0; k <= s[i] && k * v[i] <= j; k++)
                f[i][j] = max(f[i][j], f[i - 1][j - v[i] * k] + w[i] * k);
    cout << f[n][m] << endl;
    return 0;
}

// 另一种很直接的方法是
// 把第i种物品看做独立的Ci个物品，转化为∑Ci个物品的0/1背包问题
// https://www.acwing.com/problem/content/4/
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int dp[N];
int v[N], w[N], s[N], n, V;
int main(){
    cin >> n >> V;
    for (int i = 1; i <= n; i++) cin >> v[i] >> w[i] >> s[i];
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= s[i]; j++)
            for (int k = V; k >= v[i]; k--)
                dp[k] = max(dp[k], dp[k - v[i]] + w[i]);
    cout << dp[V] << '\n';
    return 0;
}

例题，多重背包问题 II，倍增

// 多重背包问题 II
// 0 < N ≤ 1000
// 0 < V ≤ 2000
// 0 < vi,wi,si ≤ 2000
// 3loops 会TLE，这里用到二进制优化（倍增思想），转化成01背包问题

一个数，可以用几个表示出来
不是一个数，恰好可以用几个表示出来，还会有一点余份，比如10，用124可以表示0-7，多来一个3，就可以表示0-10。（不能用1248来表示，因为就会表示多了，11-15也可以表示了）

// 多重背包问题 II
// O(Nlogs * V)
// 化简为O(NVlogs)
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 25000, M = 2010;
int n, m;
int v[N], w[N];
int f[N];
int main()
{
    cin >> n >> m;
    int cnt = 0;
    for (int i = 1; i <= n; i++)
    {
        int a, b, s;
        cin >> a >> b >> s;
        int k = 1;
        while (k <= s)
        {
            cnt++;
            v[cnt] = a * k;
            w[cnt] = b * k;
            s -= k;
            k *= 2;
        }
        if (s > 0)
        {
            cnt++;
            v[cnt] = a * s;
            w[cnt] = b * s;
        }
    }
    n = cnt;
    for (int i = 1; i <= n; i++)     // 这个n是 原n*logs
        for (int j = m; j >= v[i]; j--)
            f[j] = max(f[j], f[j - v[i]] + w[i]);
    cout << f[m] << endl;
    return 0;
}

// define multiplepack
#include <iostream>
using namespace std;
const int N = 1010, M = 2010;
int n, m;
int v[N], w[N], s[N];
int f[M];
void zeroonepack(int f[], int vi, int wi)
{
    for (int j = m; j >= vi; j--)
        f[j] = max(f[j], f[j - vi] + wi);
}
void completepack(int f[], int vi, int wi)
{
    for (int j = vi; j <= m; j++)
        f[j] = max(f[j], f[j - vi] + wi);
}
void multiplepack(int f[], int vi, int wi, int si)
{
    if (vi * si >= m){
        completepack(f, vi, wi);
        return ;
    }
    int k = 1;
    while (k < si){
        zeroonepack(f, k*vi, k*wi);
        si -= k;
        k *= 2;
    }
    if (si){
        zeroonepack(f, si*vi, si*wi);
    }
}
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++){
        cin >> v[i] >> w[i] >> s[i];
        multiplepack(f, v[i], w[i], s[i]);
    }
    cout << f[m] << endl;
    return 0;
}

例题，多重背包问题 III，单调队列优化

// 多重背包问题 III
// 0<N≤1000
// 0<V≤20000
// 0<vi,wi,si≤20000
// O(NVlogs)也会爆缸
// 需要使用单调队列优化方法
// 单调队列优化，O(NV)

多重背包问题 I
 for(int i=1;i<=n;i++) 
  for(int j=0;j<=m;j++)
   for(int k=0;k<=s[i]&&k*v[i]<=j;k++)
    f[i][j]=max(f[i][j],f[i-1][j-v[i]*k]+w[i]*k);
即枚举到第i个物品时,要将f[0~m]的状态全部都更新一遍.
状态转移方程为:
f[i][j]=max(f[i-1][j],f[i-1][j-v]+w,f[i-1][j-2v]+2w,...,f[i-1][j-sv]+sw);
这样的时间复杂度过大
f[i][j]=max(f[i-1][j],f[i-1][j-v]+w,f[i-1][j-2v]+2w,...,f[i-1][j-sv]+sw);
f[i][j-v]=max(f[i-1][j-v],f[i-1][j-2v]+w,f[i-1][j-3v]+2w,...,f[i-1][j-(s+1)v]+sw);
f[i][j-v]+w=max(f[i-1][j-v]+w,f[i-1][j-2v]+2w,...,f[i-1][j-sv]+sw,f[i-1][j-(s+1)]+(s+1)w);
无法像完全背包一样进行优化
完全背包 是一口气把所有体积全部用掉，即
max(a,b,c,d)=max(a,max(b,c,d))
多重背包 对于每个物品的个数是有限制的，导致我们最终的等式是如下样子：
max(a,b,c,d)≠max(a,max(b,c,d,e))
不能像完全背包那样进行推式子，进行优化

我们可以把这个式子 继续 推导下去，直到背包体积被用到不能再用为止

其中 r = j mod vi，
也可以理解为 完全背包 下把当前物品 选到不能再选 后，剩下的 余数
得到 f(i,r)=f(i−1,r)后，我们再利用 完全背包优化思路 往回倒推一遍
会惊奇的发现一个 滑动窗口求最大值 的模型
为了方便观察，我们把 f(i−1,j)改写成 fj

为了方便观察
去掉 w，然后把数组展开成一条链

于是通过该滑动窗口 ，我们就能在线性的时间里求出
第 i 阶段里，所有满足 j ≡ r mod v 的 f(i,j)
滑动窗口 求最大值的实现，只需利用队列在队头维护一个最大值的单调递减的单调队列即可
为了更新所有 i 阶段里的状态 f(i,j)，我们只需再额外枚举所有的余数r即可

滑动窗口内部比较最大值的时候，有一个在之前为了方便观察，被删掉的偏移量 w
要记得加上再比较
具体就是 当前下标 和该 最大值的下标 之间差了 x 个 v，那么就要加上 x 个 w

int f[N], g[N];    // f[]存储的是第i层,g[]存储第i-1层,
int q[N];          // q[]存储的是f、g数组中的下标(体积);

#include <bits/stdc++.h>
using namespace std;
const int N = 2e4 + 10;
int f[N], g[N];    // f[]存储的是第i层,g[]存储第i-1层,
int q[N];          // q[]存储的是f、g数组中的下标(体积);
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++){
        int v, w, s;
        scanf("%d%d%d", &v, &w, &s);
        memcpy(g, f, sizeof g);               // 备份上一层的结果
        for(int r = 0; r < v; r++){           // 枚举余数
            int tt = -1, hh = 0;           // tt代表队尾,hh代表对头(最前面的元素)
            // 在余数固定的基础上枚举可以用的值
            // j枚举体积,单调队列模板
            for(int j = r; j <= m; j += v){
                while(hh <= tt && q[hh] < j-s*v) hh++;   
                // 判断是否超出了s件物品;
                if (hh <= tt) f[j] = max(f[j], g[q[hh]] + (j - q[hh]) / v * w);
                // max(f[i-1][j], f[i-1][能转移里最大] + 个数*wi)
                // q[hh]存的是最大值对应的下标是多少, 就是体积
                // g[q[hh]]存的就是这个体积能代表的最大价值
                // 窗口内的最大值 + 收益(放了多少个物品)
                while(hh <= tt && g[q[tt]] - (q[tt] - r) / v * w <= g[j] - (j - r) / v * w) tt--;
                // 维护单调性
                // q[tt]存的值刨去 (q[tt]-r)/v*w，小于当前g[j]刨去 (j-r)/v*w
                // q[tt]存的值(这个位置)，就没有意义了
                // (q[tt]-r)/v表示个数，(j-r)/v也表示个数
                q[++tt] = j; 
            }
        }
    }
    cout << f[m] << endl;//输出最终结果
    return 0;
}

while(hh <= tt && g[q[tt]] - (q[tt] - r) / v * w <= g[j] - (j - r) / v * w) tt--;
// 每次入队的值是 g[j+k*v] - k*w，对这段代码的进一步解释
m 一定等于 k*v + r，其中  0 <= r < v
所以，我们可以把 dp 数组分成 r 个类，每一类中的值，都是在同类之间转换得到的
这些r个类的并集就是0~m
问题就变成了r个单调队列的问题
所以，我们可以得到
g[r]    =     g[r]
g[r+v]  = max(g[r] +  w,  g[r+v])
g[r+2v] = max(g[r] + 2w,  g[r+v] +  w, g[r+2v])
g[r+3v] = max(g[r] + 3w,  g[r+v] + 2w, g[r+2v] + w, g[r+3v])
...
但是，这个队列中前面的数，每次都会增加一个 w ，所以我们需要做一些转换
g[r]    =     g[r]
g[r+v]  = max(g[r], g[r+v] - w) + w
g[r+2v] = max(g[r], g[r+v] - w, g[r+2v] - 2w) + 2w
g[r+3v] = max(g[r], g[r+v] - w, g[r+2v] - 2w, g[r+3v] - 3w) + 3w
...
这样，每次入队的值是 g[r+k*v] - k*w
所以，我们在单调队列更新队尾的时候，进行的比较是
g[q[tt]] - (q[tt] - r) / v * w <= g[j] - (j - r) / v * w

// 无注释版本
#include <bits/stdc++.h>
using namespace std;
const int N = 2e4 + 10;
int f[N], g[N];    // f[]存储的是第i层,g[]存储第i-1层,
int q[N];          // q[]存储的是f、g数组中的下标(体积);
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++){
        int v, w, s;
        scanf("%d%d%d", &v, &w, &s);
        memcpy(g, f, sizeof g);               
        for(int r = 0; r < v; r++){           // 枚举余数
            int tt = -1, hh = 0;           
            for(int j = r; j <= m; j += v){
                while(hh <= tt && q[hh] < j-s*v) hh++;   
                if (hh <= tt) f[j] = max(f[j], g[q[hh]] + (j - q[hh]) / v * w);
                while(hh <= tt && g[q[tt]] - (q[tt] - r) / v * w <= g[j] - (j - r) / v * w) tt--;
                q[++tt] = j; 
            }
        }
    }
    cout << f[m] << endl;
    return 0;
}

混合三种背包问题

01背包

def ZeroOnePack(F, C, W ) 
    for v = V to C
        F[v] = max(F[v],f[v − C] + W)
for i = 1 to N 
    ZeroOnePack(F, Ci, Wi)

完全背包

def CompletePack(F, C, W ) 
    for v = C to V
        F[v] = max{F[v],f[v − C] + W}

多重背包

def MultiplePack(F, C, W, M) 
    if C·M ≥ V
        CompletePack(F, C, W)
        return
    k := 1
    while k < M
        ZeroOnePack(kC, kW) M := M − k
        k := 2k
    ZeroOnePack(C·M, W·M)

01背包+完全背包的混合

for i = 1 to N
    if 第i件物品属于01背包
        for v = V to Ci
            F[v] = max(F[v],F[v − Ci] + Wi)
    else if 第i件物品属于完全背包
        for v = Ci to V
            F[v] = max(F[v],F[v − Ci] + Wi)

01背包+完全背包+多重背包的混合

for i = 1 to N
    if 第i件物品属于01背包
        ZeroOnePack(F ,Ci ,Wi ) 
    else if 第i件物品属于完全背包
        CompletePack(F ,Ci ,Wi )
    else if 第i件物品属于多重背包 
        MultiplePack(F ,Ci ,Wi ,Ni )

例题，混合背包问题

#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int n, m;
int f[N];
int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        int v, w, s;
        cin >> v >> w >> s;
        if (s == 0) //完全背包
        {
            for (int j = v; j <= m; j++) f[j] = max(f[j], f[j - v] + w);
        }
        else
        {
            if (s == -1) s = 1;
            for (int k = 1; k <= s; k *= 2)
            {
                for (int j = m; j >= k * v; j--)
                    f[j] = max(f[j], f[j - k * v] + k * w);
                s -= k;    
            }
            if (s)
            {
                for (int j = m; j >= s * v; j--)
                    f[j] = max(f[j], f[j - s * v] + s * w);
            }
        }
    }
    cout << f[m] << endl;
    return 0;
}
// 也可以存起来，再来一遍
#include <bits/stdc++.h>
using namespace std;
const int N = 40, M = 220, MM = 1e5 + 10;
int dp[N][M], w[N], v[N], s[N];
int V, n;
int f[MM], nw[MM], nv[MM], tot, knap[MM];
int main()
{
    cin >> V >> n;
    for (int i = 1; i <= n; i++){
        cin >> w[i] >> v[i] >> s[i];
        if (s[i] == 0){
            nw[++tot] = w[i]; nv[tot] = v[i];
            knap[tot] = 1;    //完全背包
        }
        else if (s[i] == 1){   //01背包
            nw[++tot] = w[i]; nv[tot] = v[i];
        }
        else{    //多重背包
            for (int j = 1; j <= s[i]; j = j << 1){
                s[i] -= j;
                nw[++tot] = w[i] * j; nv[tot] = v[i] * j;
            }
            if (s[i]){
                nw[++tot] = w[i] * s[i]; nv[tot] = v[i] * s[i];
                s[i] = 0;
            }
        }
    }
    for (int i = 1; i <= tot; i++){
        if (knap[i]){
            for (int j = nw[i]; j <= V; j++)
                f[j] = max(f[j], f[j - nw[i]] + nv[i]);
        }
        else{
            for (int j = V; j >= nw[i]; j--)
                f[j] = max(f[j], f[j - nw[i]] + nv[i]);
        }
    }
    cout << f[V] << '\n';
    return 0;
}

// define zeroonepack(),completepack(),multiplepack()
#include <iostream>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N], s[N];
int f[N];
void zeroonepack(int f[], int vi, int wi)
{
    for (int j = m; j >= vi; j--)
        f[j] = max(f[j], f[j - vi] + wi);
}
void completepack(int f[], int vi, int wi)
{
    for (int j = vi; j <= m; j++)
        f[j] = max(f[j], f[j - vi] + wi);
}
void multiplepack(int f[], int vi, int wi, int si)
{
    if (vi * si >= m){
        completepack(f, vi, wi);
        return ;
    }
    int k = 1;
    while (k < si){
        zeroonepack(f, k*vi, k*wi);
        si -= k;
        k *= 2;
    }
    if (si){
        zeroonepack(f, si*vi, si*wi);
    }
}
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++){
        cin >> v[i] >> w[i] >> s[i];
        if (s[i] == -1) zeroonepack(f, v[i], w[i]);
        else if (s[i] == 0) completepack(f, v[i], w[i]);
        else multiplepack(f, v[i], w[i], s[i]);
    }
    cout << f[m] << endl;
    return 0;
}

二维费用背包

例题，二维费用的背包问题

#include <iostream>
using namespace std;
const int N = 110;
int n, V, M;
int f[N][N];
int main()
{
    cin >> n >> V >> M;
    for (int i = 0; i < n; i++)
    {
        int v, m, w;
        cin >> v >> m >> w;
        for (int j = V; j >= v; j--)
            for (int k = M; k >= m; k--)
                f[j][k] = max(f[j][k], f[j - v][k - m] + w);
    }
    cout << f[V][M] << endl;
    return 0;
}

例题，1271：【例9.15】潜水员

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int dp[N][25][90];
int v1[N], v2[N], w[N];
int n, m, s;
int main()
{
    cin >> n >> m >> s;
    for (int i = 1; i <= s; i++)
        cin >> v1[i] >> v2[i] >> w[i];
    memset(dp, 0x3f, sizeof dp);
    dp[0][0][0] = 0;
    for (int i = 1; i <= s; i++)
        for (int j1 = 0; j1 <= n; j1++)
            for (int j2 = 0; j2 <= m; j2++){
                dp[i][j1][j2] = dp[i - 1][j1][j2];
                dp[i][j1][j2] = min(dp[i][j1][j2], 
                                        dp[i - 1][max(0, j1 - v1[i])][max(0, j2 - v2[i])] + w[i]);
            }
    cout << dp[s][n][m] << '\n';
    return 0;
}

分组背包

例题，分组背包问题

// 这个问题变成了每组物品有若干种策略:是选择本组的某一件，还是一件 都不选
// 这里三层循环的顺序保证了每一组内的物品最多只有一个会被添加到背包中
// 分组的背包问题将彼此互斥的若干物品称为一个组，这建立了一个很好的模型
// 不少背包问题的变形都可以转化为分组的背包问题
// 由分组的背包问题进一步可定义“泛化物品”的概念，十分有利于解题
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 110;
int n, m;
int v[N][N], w[N][N], s[N];
int f[N];
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        cin >> s[i];
        for (int j = 0; j < s[i]; j++)
            cin >> v[i][j] >> w[i][j];
    }
    for (int i = 1; i <= n; i++)
        for (int j = m; j >= 0; j--)
            for (int k = 0; k < s[i]; k++)
                if (v[i][k] <= j)
                    f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
    cout << f[m] << endl;
    return 0;    
}