背包

背包问题的大致描述如下：

有 $n$ 个物品和一个容量为 $v$ 的背包，每个物品有体积 $v_i$ 和价值 $w_i$ 两种属性，要求选若干物品放入背包使背包中物品的总价值最大且背包中物品的总重量不超过背包的容量。

背包问题也被分成了很多类，例如：0-1 背包、完全背包、多重背包、分组背包、混合背包、有依赖的背包。求解还被分为求最大值，最小值，恰好值，方案数，具体方案。

0-1背包

0-1 背包问题的特点是每个物品只能使用一次。

dp 问题的本质其实也是暴力，只不过利用了前者的经验，省去了一部分力气。 一般考虑 dp 问题首先确定我们问题的状态表示，也就是多维数组的维数和意义。而 0-1 背包是 $f(i, j)$ 表示在前 $i$ 个选取物品且体积不超过 $j$ 的情况下最大价值。然后再考虑，如何计算 $f(i, j)$。这里考虑问题一定要向递归的方向思考，利用前者的结果来想，否则是无法直接计算 $f(i, j)$ 的。而递归都是怎么想的？比较熟悉的组合数的递归公式是

$${n \choose k} = {n-1 \choose k-1} + {n-1 \choose k}$$

看到这就应该懂了，考虑递归的话要利用之前的经验。那么 $f(i,j)$ 由于体积的限制，当我要取第 $i$ 的时候，可以分为由于装不下第 $i$ 个物品而不取第 $i$ 个和满足体积要求取第 $i$ 个。不取第 $i$ 个的值为 $f(i-1,j)$，取第 $i$ 个的话那么体积要减少价值会增加，其值为 $f(i-1,j-v)+w$。

$$f(i,j) = max(f(i-1,j),\ f(i-1,j-v_i) + w_i)$$

二维空间代码：

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1010;
int v[N],w[N];
int dp[N][N];

int main(){
    int n, m; 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 = 1; j <= m; j ++){
            dp[i][j] = dp[i - 1][j];
            if (j >= v[i]) dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i]] + w[i]);
        }
    cout << dp[n][m];
}

其实还可以进行降维优化，由于更新第 $i$ 层时只用了第 $i-1$ 并且更新每个 $j$ 时用到的数据都是之前的数据，可以利用滚动数组来优化。

一维空间代码：

此时的状态数组的含义变为了在 i 体积下，物品的最大值为多少。

// input
// 4 5
// 1 2
// 2 4
// 3 4
// 4 5
// output
// state update
// 0 2 2 2 2 2 
// 0 2 4 6 6 6 
// 0 2 4 6 6 8 
// 0 2 4 6 6 8 
// 8
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1010;
int v[N],w[N];
int dp[N]; //

int main(){
    int n, m; 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 --)
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
            
    cout << dp[m];
}

完全背包

完全背包的特点是每个物品无限次使用。 相同与 0-1 背包问题的分析方法。

• 状态表示 $f(i,j)$ 表示选取前 $i$ 个物品中体积不超过 $j$ 的最大价值。

• 状态计算 当不选第 $i$ 件物品时，$f(i,j) = f(i-1,j)$。 当选第 $i$ 件物品时，可以任意的选取第 $i$ 件物品，既 $f(i,j)=f(i-1,j-k*v)+k*w$。

$$f(i,j) = max(f(i-1,j), f(i-1, j-k*v_i) + k*w_i)$$

不过真用这个式子来计算的话会超时。考虑

$$\begin{cases} f(i,j) &= max(f(i-1,j),&f(i-1,j-v)+w,&f(i-1,j-2v)+2w,\cdots) \\ f(i,j-v) &= max(&f(i-1,j-v),&f(i-1,j-2*v)+w,\cdots) \end{cases}$$

可得

$$f(i, j) = max(f(i-1,j), f(i, j-v_i) + w_i)$$

二维

#include<iostream>
#include<algorithm>
using namespace std;

const int N = 1010;

int v[N], w[N];
int dp[N][N];

int main(){
    int n, m; cin >> n >> m;
    for (int i = 1; i <= n; i ++) scanf("%d %d", &v[i], &w[i]);
    
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= m; j ++){
            dp[i][j] = dp[i - 1][j];
            if (j >= v[i]) dp[i][j] = max(dp[i][j], dp[i][j - v[i]] + w[i]);
        }
    cout << dp[n][m];
}

一维

#include<iostream>
#include<algorithm>
using namespace std;

const int N = 1010;

int v[N], w[N];
int dp[N];

int main(){
    int n, m; cin >> n >> m;
    for (int i = 1; i <= n; i ++) scanf("%d %d", &v[i], &w[i]);
    
    for (int i = 1; i <= n; i ++)
        for (int j = v[i]; j <= m; j ++)
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);

    cout << dp[m];
}

多重背包

多重背包的特点是背包数量不定。

• 状态表示 $f(i,j)$ 表示前 $i$ 个物品体积不超过 $j$ 的最大价值。

• 状态计算 当不选第 $i$ 种物品，则 $f(i,j) = f(i-1, j)$ 当选第 $i$ 种物品，则 $f(i,j) = f(i - 1, j - k*v)+k*w$

$$f(i,j) = max(f(i-1,j), f(i - 1, j - k * v_i) + k * w_i)$$

二维

#include<iostream>
#include<algorithm>
using namespace std;

const int N = 1010;

int v[N], w[N], s[N];
int dp[N][N];

int main(){
    int n, m; cin >> n >> m;
    for (int i = 1; i <= n; i ++) scanf("%d %d %d", &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 ++){
                dp[i][j] = max(dp[i][j], dp[i - 1][j - k * v[i]] + k * w[i]);
            }
            
    cout << dp[n][m] << endl;
}

多重背包可以优化，可以使用滚动数组优化。

一维

#include<iostream>
using namespace std;

const int N = 110;

int f[N];

int main() {
    int n, m; cin >> n >> m;
    
    for (int i = 0; i < n; i ++) {
        int v, w, s; cin >> v >> w >> s;
        
        for (int j = m; j >= v; j --) {
            for (int k = 0; k <= s && k * v <= j; k ++) {
                f[j] = max(f[j], f[j - k * v] + k * w);
            }
        }
    }
    
    cout << f[m] << endl; 
}

二进制优化

也可以二进制优化，将多重背包优化为 0-1 背包。考虑单个种类的物品，假设此种类的物品的数量为 $N$，我们要选取此种类的物品的数量为 $x$。难道我们要像完全背包那样从 $0 \sim N$ 枚举来获得 $x$ 吗？可以但没必要。 我们可以将此类物品打包成数量为 $1+2+4+\cdots+ c = N$，举个例子：

$$6 = 1 + 2 + 3 \\ 18 = 1 + 2 + 4 + 8 + 3$$

通过这样打包，我们可以使用这些包装过的物品能够凑出选取 $0 \sim N$ 的所有数量的物品，而且使用每个包装的数量为 $0$ 或者 $1$，完美满足 0-1 背包的性质。这样就可以转化为 0-1 背包的问题。

#include<iostream>
#include<algorithm>
using namespace std;

const int N = 15000;
int v[N], w[N];
int f[N];

int main(){
    int n, m; 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 <<= 1;
        }
        if (s > 0) {
            cnt ++;
            v[cnt] = a * s;
            w[cnt] = b * s;
            
        }
    }
    n = cnt;
    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]);
            
    cout << f[m] << endl;
}

单调队列优化

#include<iostream>
#include<cstring>
using namespace std;

const int N = 20010;

int f[N], g[N], q[N];

int main() {
    int n, m; cin >> n >> m;
    
    for (int i = 0; i < n; i ++) {
        int v, w, s; cin >> v >> w >> s;
        memcpy(g, f, sizeof f);
        for (int j = 0; j < v; j ++) {
            int h = 0, t = -1;
            for (int k = j; k <= m; k += v) {
                if (h <= t && q[h] < k - s * v) h ++;
                if (h <= t) f[k] = max(g[k], g[q[h]] + (k - q[h]) / v * w);
                while (h <= t && g[k] >= g[q[t]] + (k - q[t]) / v * w) t --;
                q[++ t] = k;
            }
        }
    }
    cout << f[m];
}

分组背包

分组背包的特点是每个组有多个种类物品，但每个组只选取一个物品

• 状态分析 $f(i,j)$ 表示前 $i$ 组物品体积不超过 $j$ 的最大价值。

• 状态计算 不选取第 $i$ 组物品，$f(i,j) = f(i-1, j)$ 选取第 $i$ 组物品，$f(i,j) = f(i-1,j - v[i,k]) + w[i,k]$

$$f(i,j) = max(f(i-1,j),f(i-1,j - v[i,k]) + w[i,k])$$

#include<iostream>
#include<algorithm>
using namespace std;

const int N = 110;

int v[N][N], w[N][N];
int s[N];
int f[N];

int main(){
    int n, m; cin >> n >> m;
    for (int i = 1; i <= n; i ++ ){
        int k; cin >> k;
        s[i] = k;
        for (int j = 1; j <= k; 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 = 1; k <= s[i]; k ++)
                if (j >= v[i][k])
                    f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
    
    cout << f[m] << endl;
                
}

混合背包

混合背包集合了 0-1 背包、完全背包和多种背包，我们需要在一题里解决他们所有的状态转移。

这题把多重背包进行二进制优化拆解成 0-1 背包，最后本别做 0-1 背包和完全背包状态转移。

#include<iostream>
using namespace std;

const int N = 12000;

int f[N];
int a[N], b[N], c[N];

int main() {
    int n, m; cin >> n >> m;
    int t = 1;
    for (int i = 0; i < n; i ++) {
        int v, w, s; cin >> v >> w >> s;
        if (!s) {
            a[t] = v;
            b[t] = w;
            c[t ++] = 1;
        } else {
            if (s == -1) {
                s = 1;
            }
            int num = 1;
            while (num <= s) {
                a[t] = num * v;
                b[t ++] = num * w;
                s -= num;
                num *= 2;
            }       
            if (s > 0) {
                a[t] = s * v;
                b[t ++] = s * w;
            }
        }
    }
    n = t; 
    for (int i = 1; i < n; i ++) {
        if (!c[i]) {
            for (int j = m; j >= a[i]; j --) {
                f[j] = max(f[j], f[j - a[i]] + b[i]);
            }
        } else {
            for (int j = a[i]; j <= m; j ++) {
                f[j] = max(f[j], f[j - a[i]] + b[i]);
            }
        }
    }
    cout << f[m];
}

有依赖的背包问题

有依赖的背包问题指的是背包之间有着依赖关系，在选择背包时，不仅仅考虑体积还有他们之间的关系。

我们先把背包关系构成一颗树，考虑当选择当前节点时，如何选择子节点。我们可以认为每个子节点为一组背包，因为我们可能会选择子节点一定体积的背包。

然后我们可以通过 dfs 遍历节点，再回溯，对每个节点做分组背包。 我们的 $f[i][j]$ 可以考虑为，选择了第 i$$$ 的背包的同时体积不超过 j$$ 的最大值。

#include<iostream>
#include<vector>

using namespace std;

const int N = 110;

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

vector<vector<int>> p(N);

void dfs(int u) {
    for (int i = v[u]; i <= m; i ++) {
        f[u][i] = w[u];
    }
    for (auto x: p[u]) {
        dfs(x);
        for (int j = m; j >= v[u]; j --) {
            for (int k = 0; k <= j - v[u]; k ++) {
                f[u][j] = max(f[u][j], f[u][j - k] + f[x][k]);
            }
        }
    }
}

int main() {
    cin >> n >> m;
    int head = 0;
    for (int i = 1; i <= n; i ++) {
        cin >> v[i] >> w[i];
        int a; cin >> a;
        if (a == -1) {
            head = i;
        } else {
            p[a].push_back(i);
        }
    }
    dfs(head);
    cout << f[head][m];
}

背包问题求方案数

考虑正常 0-1 背包时的状态转移，我们分配所有的体积可能性，看每个背包选还是不选。

那么我们的最优方案数可以考虑，当背包选不选时，那个可以获得更大的值进行转移。

我们定义数组 $f[i]$，代表在体积为 i 时的最大价值；数组 $c[i]$，代表在体积为 i 时最优方案数。

#include<iostream>
using namespace std;

const int N = 1010, mod = 1e9 + 7;
int f[N], c[N];

int main() {
    int n, m; cin >> n >> m;
    for (int i = 0; i <= m; i ++) {
        c[i] = 1;
    }
    for (int i = 1; i <= n; i ++) {
        int v, w; cin >> v >> w;
        for (int j = m; j >= v; j --) {
            if (f[j - v] + w > f[j]) {
                f[j] = f[j - v] + w;
                c[j] = c[j - v];
            } else if (f[j - v] + w == f[j]) {
                c[j] = (c[j] + c[j - v]) % mod;
            }
        }
    }
    cout << c[m] << endl;
}

背包问题求具体方案

先进行状态转移，再从最大值开始进行状态回溯。

#include<iostream>
using namespace std;

const int N = 1010;

int f[N][N], v[N], w[N];

int main() {
    int n, m; cin >> n >> m;
    for (int i = 1; i <= n; i ++) {
        cin >> v[i] >> w[i];
    }
    for (int i = n; i > 0; 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 + 1][j - v[i]] + w[i]);
            }
        }
    }
    int j = m;
    for (int i = 1; i <= n; i ++) {
        if (j >= v[i] && f[i][j] == f[i + 1][j - v[i]] + w[i]) {
            cout << i << ' ';
            j -= v[i];
        }
    }
}