背包问题

背包问题是一类经典的动态规划问题，可以简单（数据量不大时）也可以很复杂（数据量很大时）。下面介绍几种典型背包问题，可以当做模板。

01背包问题

给定n个物品和一个容量为v的背包，求背包能装下的最大价值。特点是每个物品最多只能选择一次。

思考过程：

# include <bits/stdc++.h>
using namespace std;

int main() {
    int N, V;
    cin >> N >> V;
    vector<int> volumes(N + 1), values(N + 1);
    for (int i = 1; i <= N; i++) {
        cin >> volumes[i] >> values[i];
    }
    // 先写最好想的多维动态规划——观察写好的多维dp，其实可以优化到一维，因为好多历史状态并没有用上
    // 核心历史状态是当前容量j
    vector<int> dp(V + 1, 0); // dp[i]表示当前背包容量为i时的最大价值
    // int ans = 0;
    for (int i = 1; i <= N; i++) {
        // 考虑前i件物品
        for (int j = V; j >= 1; j--) {
            // dp[j]就是当前容量为j的背包
            if (j >= volumes[i]) {
                // 选or不选, 取决于是选的更大还是不选的更大
                dp[j] = max(dp[j], dp[j - volumes[i]] + values[i]); // 前者保持不选，后者选
                // 注意到后面这个表达式用到了dp[j-volumes[i]]，显然我们需要的是选第i件物品之前的dp，所以较小的dp会被较大的dp用到“老”值，因此更新时要从大到小更新，确保小的被用到时是旧值
                // 而大dp不会被小dp用到，所以先更新没有问题
            }
        }
    }
    // 肯定是容量越大越好
    cout << dp.back();
}

板子：

# include <bits/stdc++.h>
using namespace std;

int main() {
    int N, V;
    cin >> N >> V;
    vector<int> dp(V + 1, 0);
    for (int i = 1; i <= N; i++) {
        int volume, value;
        cin >> volume >> value;
        // 倒序遍历确保大容量dp用到的小容量dp是旧值,
        // 同时循环内if判断可以挪到for里，因为只有当前容量大于等于物品体积时当前容量的价值才有可能变化
        for (int j = V; j >= volume; j--) {
            dp[j] = max(dp[j], dp[j - volume] + value);
        }
    }
    cout << dp.back() << endl;
    return 0;
}

完全背包问题

1. 完全背包问题的定义：给定一个背包容量和一组物品，每个物品可以选择多次，求最大价值。

2. 完全背包问题的状态转移方程：$dp[i][j] = max(dp[i-1][j], dp[i][j-w[i]] + v[i])$，其中$w[i] 和 v[i]$分别是第$i$个物品的重量和价值。

当然这个二维也是可以优化到一维的，见代码:

# include <bits/stdc++.h>
using namespace std;

int main() {
    int N, V;
    cin >> N >> V;
    vector<int> dp(V + 1, 0);
    for (int i = 0; i < N; i++) {
        // 考虑第i件物品
        int value, volume;
        cin >> volume >> value;
        for (int j = volume; j <= V; j++) { // 注意这里与01背包不同，是从小到大顺序遍历的，而不是逆序，因为物品数量无限可以任意选
            // 所以i选了之后还嫩还能再选i，对于二维情况就是[i][j]=max([i][j], [i][j-v]), 所以大dp用到的小dp必须是新dp[i]而不能是旧的dp[i-1]
            // 所以必须从小到大，不然用到旧dp[i-1]的话就会漏情况
            // 至少要能放下一个
            dp[j] = max(dp[j], dp[j - volume] + value);
        }
    }
    cout << dp.back() << endl;
    return 0;
}

多重背包问题

这里是背包问题的重灾区之一，是对上面两个元问题的综合运用及运用各种优化手段。

I阶

问题主体和01背包问题一致，区别在于每种物品的数量不止1件，其他条件保持一致。数据量较小 $N,V\le100$, 即使$O(n^3)$也不会超时

# include <bits/stdc++.h>
using namespace std;

int main() {
    int N, V;
    cin >> N >> V;
    vector<int> volumes(N), values(N), count(N);
    for (int i = 0; i < N; i++) {
        cin >> volumes[i] >> values[i] >> count[i];
    }
    // 一般来说只要选了一件物品，就会一直选到背包放不下为止
    // 所以可以硬“拆”成01背包问题, 关键是怎么拆
    // 拆的思想也很朴素：当只有一件物品时，相当于01背包问题，当有多件时，视为多个一件物品（即同一种物品当作不同种，还是每种一件）
    vector<int> new_values = values, new_volumes = volumes;
    for (int i = 0; i < N; i++) {
        while (count[i] > 1) {
            // 拆分数量大于1的物品
            new_values.push_back(values[i]);
            new_volumes.push_back(volumes[i]);
            count[i]--;
        }
    }
    values = new_values;
    volumes = new_volumes;
    vector<int> dp(V + 1, 0); // dp[i]还是背包容量为i时的最大价值
    // 直接套模板
    for (int i = 0; i < values.size(); i++) {
        // 还是倒序遍历
        for (int j = V; j >= volumes[i]; j--) {
            // 进来的都是能放下一个物品的，因为循环保证了容量足够的才会进行下去
            dp[j] = max(dp[j], dp[j - volumes[i]] + values[i]);
        }
    }
    cout << dp.back();
    return 0;
}

II阶

问题与多重背包问题 I 完全一致，但数据范围变大了 $N,V \le 1000$，不能简单地暴力拆分循环了

# include <bits/stdc++.h>
using namespace std;

// 优化：二进制优化
// 原来的完全拆分最后的物品数都是1，用这些1来组合原来0~n中的任何一种可能数量取值，但这样的复杂度是O(n)
// 不难想到，一个数在计算机中的表示其实是二进制而非一个一个1，所有可以利用二进制的思路来表示这些数量的取值，而不是用很多1
// 比如11，原来的拆分法就是拆成11个相同的物品（视作11种物品），也就是11个1
// 但是11可以拆分为1，2，4，4（二进制表示，4重复一次方便表示大于等于8的数，且所有数求和不超过11，代表数量受限）
// 这样四个数也可以表示0~11的所有数，但复杂度只有O(nlogn)
// 那么问题就变成了怎么做二进制拆分，见代码

int main() {
    int N, V;
    cin >> N >> V;
    vector<int> volumes, values, count;
    for (int i = 0; i < N; i++) {
        int vo, va, co;
        cin >> vo >> va >> co;
        bool found = false;
        for (int j = 0; j < values.size(); j++) {
            if (volumes[j] == vo && values[j] == va) {
                count[j] += co;
                found = true;
                break;
            }
        }
        if (!found) {
            values.push_back(va);
            volumes.push_back(vo);
            count.push_back(co);
        }
    }
    N = values.size();
    // 可以硬“拆”成01背包问题, 关键是怎么拆
    vector<int> new_volumes, new_values; // count可以合并到价值和体积里，比如3个就是价值和体积都乘3
    for (int i = 0; i < N; i++) {
        // 二进制拆分，同时更新价值和体积
        int base = 1;
        while (count[i] > 0) {
            if (count[i] < base) {
                base = 1;
                continue;
            }
            count[i] -= base;
            new_values.push_back(values[i] * base);
            new_volumes.push_back(volumes[i] * base);
            base *= 2;
        }
    }
    values = new_values, volumes = new_volumes;
    vector<int> dp(V + 1, 0);
    for (int i = 0; i < values.size(); i++) {
        // 枚举前i件物品
        for (int j = V; j >= volumes[i]; j--) {
            dp[j] = max(dp[j], dp[j - volumes[i]] + values[i]);
        }
    }
    // 容量越大越好
    cout << dp.back() << endl;
    return 0;
}

III阶

III阶很难，有余力再来掌握吧，花了很久看题解也并没有完全理解代码部分

问题与多重背包问题 II 完全一致，但数据范围更大了, $N\le 1000,~V \le 20000$

本题的优化思路疑似有点太复杂了，贴一下 ref

# include <bits/stdc++.h>
// 有必要的话开O2，stl可能会超时
// %:pragma GCC optimize(3)
using namespace std;

int main() {
    int N, V;
    cin >> N >> V;
    vector<int> volumes(N), values(N), count(N);
    for (int i = 0; i < N; i++) {
        cin >> volumes[i] >> values[i] >> count[i];
    }
    vector<int> dp1(V + 1, 0), dp2(V + 1, 0); // 两个dp数组用来维护当前状态和前一轮状态，利用拷贝数组的思想来保存状态
    deque<int> q; // 单调队列
    for (int i = 0; i < N; i++) {
        dp2 = dp1; // 获取前一轮dp1的状态, 当前轮继续更新dp1
        // 枚举物品i所有的余数（一直到自己的体积）
        for (int mod = 0; mod < volumes[i]; mod++) {
            // 枚举每个余数，从mod到mod + k * v[i], 不超过背包容量
            q.clear(); // 清空队列
            for (int j = mod; j <= V; j += volumes[i]) {
                while (!q.empty() && j - q.front() > count[i] * volumes[i]) {
                    q.pop_front(); // 弹出队头元素，直到队头元素满足条件
                }
                while (!q.empty() && dp2[q.back()] + (j - q.back()) / volumes[i] * values[i] <= dp2[j]) {
                    q.pop_back(); // 弹出队尾元素，直到队尾元素满足条件, 从状态dp2转移而来
                }
                q.push_back(j);
                dp1[j] = dp2[q.front()] + (j - q.front()) / volumes[i] * values[i]; // 更新当前状态
            } 
        }
    }
    cout << dp1.back() << endl;
    return 0;
}

带依赖的背包问题

01背包的进阶版，物品之间存在依赖关系，比如如果选了a则一定要选b。问题描述如下：

有 N个物品和一个容量是 V的背包。
物品之间具有依赖关系，且依赖关系组成一棵树的形状。如果选择一个物品，则必须选择它的父节点。
第一行有两个整数 N, V, 用空格隔开，分别表示物品个数和背包容量。
接下来有 N行数据，每行数据表示一个物品。
第i行有三个整数 vi,wi,pi
用空格隔开，分别表示物品的体积、价值和依赖的物品编号。
如果 pi=−1, 表示根节点。数据保证所有物品构成一棵树

模板代码如下：

# include <bits/stdc++.h>
using namespace std;

vector<int> graph[110]; // 用邻接表表示依赖关系
int N, V, root;

// 从节点i开始深搜，也就是选以i为根节点的子树的物品
void dfs(vector<vector<int>>& dp, vector<int>& volumes, vector<int>& values, int root) {
    // 节点i是必选的，因为是子树的根节点
    for (int i = volumes[i]; i <= V; i++) {
        dp[root][i] = values[root];
    }
    for (int child : graph[root]) {
        // do dfs first
        dfs(dp, volumes, values, child);
        // 内核还是01背包问题，所以大体积要用小体积的旧值来更新
        int v = volumes[root];
        for (int i = V; i >= v; i--) {
            // j分配给子树, 那么自己(root)还剩i - j, i - j不能小于v, 不然就选不了根节点了
            for (int j = volumes[child]; i - j >= v; j++) {
                // 取 当前 -> dp[root][i] 和 自己(root)留i-j -> dp[root][i-j] 分配子树(child)j -> dp[child][j]求和 中的较大者 
                dp[root][i] = max(dp[root][i], dp[root][i - j] + dp[child][j]);
            }
        }
    }
}

int main() {
    cin >> N >> V;
    // 得先确认依赖关系
    vector<int> volumes(N + 1), values(N + 1);
    vector<vector<int>> dp(N + 1, vector<int>(V + 1, 0)); // dp[i][j]表示选以i为根节点的子树的物品且容量不超过j时取得的最大价值
    for (int i = 1; i <= N; i++) {
        int dep;
        cin >> volumes[i] >> values[i] >> dep;
        if (dep == -1) {
            root = i; // 当前是根节点
        } else {
            graph[dep].push_back(i);
        }
    }
    dfs(dp, volumes, values, root);
    cout << dp[root].back() << endl;
    return 0;
}

背包问题方案数

01背包改版，要求求出最高价值的组合方案数，问题描述如下：

有 N件物品和一个容量是V的背包。每件物品只能使用一次。
第i件物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最优选法的方案数。注意答案可能很大，请输出答案模 10e9+7的结果。

代码如下：

#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007

int main() {
    int N, V;
    cin >> N >> V;
    vector<int> dp(V + 1, 0); // 记录最大价值
    vector<int> count(V + 1, 1); // 记录该容积下最大价值的方案数, 默认方案数是1, 代表该组合成功组出了一种方案，后续会迭代更新
    for (int i = 0; i < N; i++) {
        int va, vo;
        cin >> vo >> va;
        for (int j = V; j >= vo; j--) {
            if (dp[j] < dp[j - vo] + va) {
                count[j] = count[j - vo];
                dp[j] = dp[j - vo] + va;
            } else if (dp[j] == dp[j - vo] + va) {
                count[j] += count[j - vo];
            }
            count[j] %= mod;
        }
    }
    cout << count.back() << endl;
    return 0;
}

背包问题具体方案

01背包的改版，要求求出价值最高方案的具体组合方式，相同价值时要求方案的字典序最小，问题描述如下：

有N件物品和一个容量是V的背包。每件物品只能使用一次。
第i件物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出字典序最小的方案。这里的字典序是指：所选物品的编号所构成的序列。物品的编号范围是1~N。

代码如下：

# include<bits/stdc++.h>
using namespace std;

int compare(vector<int>& a, vector<int>& b) {
    for (int i = 0; i < min(a.size(), b.size()); i++) {
        if (a[i] < b[i]) {
            return -1;
        }
        if (a[i] > b[i]) {
            return 1;
        }
    }
    return (int)a.size() - (int)b.size();
}

int main() {
    int N, V;
    cin >> N >> V;
    vector<int> dp(V + 1, 0);
    vector<vector<int>> plans(V + 1); // 容积为j时的最佳方案对应的字典序最小的组合
    for (int i = 1; i <= N; i++) {
        int vo, va;
        cin >> vo >> va;
        for (int j = V; j >= vo; j--) {
            if (dp[j] < dp[j - vo] + va) {
                dp[j] = dp[j - vo] + va;
                plans[j] = plans[j - vo];
                plans[j].push_back(i);
            } else if (dp[j] == dp[j - vo] + va) {
                vector<int> tmp = plans[j - vo];
                tmp.push_back(i);
                if (compare(tmp, plans[j]) < 0) {
                    plans[j] = move(tmp);
                }
            }
        }
    }
    for (int i : plans.back()) {
        cout << i << " ";
    }
    return 0;
}

(•‿•)