动态规划之背包问题

01背包

01背包问题

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。

第 i 件物品的体积是 vi ，价值是 wi 。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。

int n;
int v;
cin >> n >> v;
vector<int> arrV(n);
vector<int> arrW(n);
for (int i = 0; i < n; i++) {
    cin >> arrV[i];
    cin >> arrW[i];
}
vector<int> dp(v + 1, 0);
for (int i = 1; i <= n; i++)
    for (int j = v; j >= arrV[i - 1]; j--)
        dp[j] = max(dp[j], arrW[i - 1] + dp[j - arrV[i - 1]]);
cout << dp.back();

完全背包

完全背包问题

有 N 种物品和一个容量是 V 的背包，每种物品都有无限件可用。

第 i 种物品的体积是 vi ，价值是 wi 。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。

int n, v;
cin >> n >> v;
vector<int> arrV(n);
vector<int> arrW(n);
for (int i = 0; i < n; i++) {
    cin >> arrV[i];
    cin >> arrW[i];
}
vector<int> dp(v + 1, 0);
for (int i = 1; i <= n; i++)
    for (int j = arrV[i - 1]; j <= v; j++)
        dp[j] = max(dp[j], arrW[i - 1] + dp[j - arrV[i - 1]]);
cout << dp.back();

多重背包

有 N 种物品和一个容量是 V 的背包。

第 i 种物品最多有 si 件，每件体积是 vi ，价值是 wi。

求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。

朴素解法

多重背包问题1

int n, v;
cin >> n >> v;
vector<int> arrV(n);
vector<int> arrW(n);
vector<int> arrS(n);
for (int i = 0; i < n; i++) {
    cin >> arrV[i];
    cin >> arrW[i];
    cin >> arrS[i];
}
vector<int> dp(v + 1, 0);
for (int i = 1; i <= n; i++)
    for (int j = 0; j < arrS[i - 1]; j++)
        for (int k = v; k >= arrV[i - 1]; k--)
            dp[k] = max(dp[k], arrW[i - 1] + dp[k - arrV[i - 1]]);
cout << dp.back();

二进制优化

多重背包问题2

int N, V;
cin >> N >> V;
vector<int> dp(V+1);
for (int i = 0; i < N; i++) {
    int v, w, s;
    cin >> v >> w >> s;
    int k = 1;
    vector<int> arrV;
    vector<int> arrW;
    while (s >= k) {
        arrV.emplace_back(v * k);
        arrW.emplace_back(w * k);
        s -= k;
        k *= 2;
    }
    if (s > 0) {
        arrV.emplace_back(v * s);
        arrW.emplace_back(w * s);
    }
    for (int j = 0; j < arrV.size(); j++) {
        for (int z = V; z >= arrV[j]; z--) {
            dp[z] = max(dp[z], dp[z - arrV[j]] + arrW[j]);
        }
    }
}
cout << dp.back();

单调队列优化

多重背包问题3

int q[50005];//单调队列

int main() {
    int N, V;
    cin >> N >> V;
    //一个存现在状态,一个存上一个状态
    vector<vector<int>> dp(2, vector<int>(V + 1));
    int pre = 0;
    int cur = 1;
    for (int i = 0; i < N; i++) {
        pre = 1 - pre;
        cur = 1 - cur;
        int v, w, s;
        cin >> v >> w >> s;
        for (int j = 0; j < v; j++) {
            int head = 0;
            int tail = -1;
            for (int k = j; k <= V; k += v) {
                dp[cur][k] = dp[pre][k];
                while (head <= tail && q[head] < k - v * s) head++;
                if (head <= tail)
                    dp[cur][k] = max(dp[cur][k], dp[pre][q[head]] + (k - q[head]) / v * w);
                while (head <= tail && dp[pre][q[tail]] + (k - q[tail]) / v * w <= dp[pre][k])
                    tail--;
                q[++tail] = k;
            }
        }
    }
    cout << dp[cur][V];
}

混合背包

混合背包问题

有 N 种物品和一个容量是 V 的背包。

物品一共有三类：

1. 第一类物品只能用1次（01背包）；
2. 第二类物品可以用无限次（完全背包）；
3. 第三类物品最多只能用 si 次（多重背包）；
   每种体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。输出最大价值。

题解代码

int N, V;
cin >> N >> V;
vector<vector<int>> dp(2, vector<int>(V + 1));
int cur = 0;
int pre = 1;
int q[5005];//单调队列
for (int i = 0; i < N; i++) {
    pre = 1 - pre;
    cur = 1 - cur;
    int v, w, s;
    cin >> v >> w >> s;
    if (s == -1) {
        for (int j = 0; j < v; j++) dp[cur][j] = dp[pre][j];
        for (int j = v; j <= V; j++) {
            dp[cur][j] = max(dp[pre][j], dp[pre][j - v] + w);
        }
    } else if (s == 0) {
        cur = 1 - cur;
        pre = 1 - pre;
        for (int j = v; j <= V; j++) {
            dp[cur][j] = max(dp[cur][j], dp[cur][j - v] + w);
        }
    } else {
        for (int j = 0; j < v; j++) {
            int head = 0;
            int tail = -1;
            for (int k = j; k <= V; k += v) {
                dp[cur][k] = dp[pre][k];
                while (head <= tail && q[head] < k - s * v) head++;
                if (head <= tail) {
                    dp[cur][k] = max(dp[cur][k], dp[pre][q[head]] + (k - q[head]) / v * w);
                }
                while (head <= tail && dp[pre][q[tail]] + (k - q[tail]) / v * w <= dp[pre][k])
                    tail--;
                q[++tail] = k;
            }
        }
    }
}
cout << dp[cur].back() << endl;

二维费用背包

二维费用背包问题

有 N 件物品和一个容量是 V 的背包，背包能承受的最大重量是 M。

每件物品只能用一次。体积是 vi，重量是 mi，价值是 wi。

求解将哪些物品装入背包，可使物品总体积不超过背包容量，总重量不超过背包可承受的最大重量，且价值总和最大。输出最大价值。

int dp[105][105];

int main() {
    int N, V, M;
    cin >> N >> V >> M;
    memset(dp,0,sizeof(dp));
    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--) {
                dp[j][k] = max(dp[j][k], dp[j - v][k - m] + w);
            }
        }
    }
    cout << dp[V][M];
}

分组背包

分组背包问题

有 N 组物品和一个容量是 V 的背包。

每组物品有若干个，同一组内的物品最多只能选一个。每件物品的体积是 vij ，价值是 wij ，其中 i是组号，j是组内编号。

求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。输出最大价值。

int dp[105];
int v[105];
int w[105];

int main() {
    int N, V;
    cin >> N >> V;
    memset(dp, 0, sizeof(dp));
    for (int i = 0;i < N;i++) {
        int s;
        cin >> s;
        for (int j = 0;j < s;j++) {
            cin >> v[j] >> w[j];
        }
        for (int j = V;j >= 0;j--) {
            for (int k = 0;k < s;k++) {
                if (j >= v[k]) dp[j] = max(dp[j], dp[j - v[k]] + w[k]);
            }
        }
    }
    cout << dp[V] << endl;
}

有依赖的背包

有依赖的背包问题

有 N 个物品和一个容量是 V 的背包。

物品之间具有依赖关系，且依赖关系组成一棵树的形状。如果选择一个物品，则必须选择它的父节点。

每件物品的编号是 i，体积是 vi，价值是 wi，依赖的父节点编号是 pi。物品的下标范围是 1...N。

求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。输出最大价值。

const int maxN = 105;

vector<int> arr[maxN];
int dp[maxN][maxN];
int arrV[maxN];
int arrW[maxN];
int vis[maxN];
int N, V;

void dfs(int s) {
    vis[s] = 1;
    for (int i = V; i >= arrV[s]; i--) dp[s][i] = arrW[s];
    for (auto u : arr[s]) {
        if (vis[u]) continue;
        dfs(u);
        for (int i = V; i >= arrV[s]; i--)
            for (int j = 0; i - j >= arrV[s]; j++)
                dp[s][i] = max(dp[s][i], dp[s][i - j] + dp[u][j]);
    }
}

int main() {
    memset(vis, 0, sizeof(vis));
    memset(dp, 0, sizeof(dp));
    int root;
    cin >> N >> V;
    for (int i = 1; i <= N; i++) {
        int p;
        cin >> arrV[i] >> arrW[i] >> p;
        if (p == -1) root = i;
        else arr[p].emplace_back(i);
    }
    dfs(root);
    cout << dp[root][V] << endl;
}

泛化物品的背包

这种背包，没有固定的费用和价值，它的价值是随着分配给它的费用而定。在背包容量为 V 的背包问题中，当分配给它的费用为 vi 时，能得到的价值就是 h(vi)。这时，将固定的价值换成函数的引用即可。

泛化物品的背包问题

Matrix 要在下个月交给老师 n 篇论文，论文的内容可以从 m 个课题中选择。由于课题数有限，Matrix 不得不重复选择一些课题。完成不同课题的论文所花的时间不同。具体地说，对于某个课题 i，若 Matrix 计划一共写 x 篇论文，则完成该课题的论文总共需要花费 ai * X^bi 个单位时间。给定与每一个课题相对应的 ai 和 bi 的值，请帮助 Matrix 计算出如何选择论文的课题使得他可以花费最少的时间完成这 n 篇论文。

struct node {
    int a;
    int b;
};

long long F(const node& n, long long x) {
    long long ret = 1;
    int exp = n.b;
    while (exp > 0) {
        if (exp & 1) ret *= x;
        x = x * x;
        exp = exp >> 1;
    }
    return ret * n.a;
}

int N, M;
node arr[24];
long long dp[205];

int main() {
    cin >> N >> M;
    dp[0] = 0;
    for (int i = 1; i <= N; i++)
        dp[i] = INT_MAX;
    for (int i = 0; i < M; i++)
        cin >> arr[i].a >> arr[i].b;
    for (int i = 0; i < M; i++)
        for (int j = N; j >= 1; j--)
            for (int k = 1; k <= j; k++)
                dp[j] = min(dp[j], dp[j - k] + F(arr[i], k));
    cout << dp[N] << endl;
}

背包问题问法的变化

以上涉及的各种背包问题都是要求在背包容量（费用）的限制下求可以取到的最大价值，但背包问题还有很多种灵活的问法，在这里值得提一下。但是我认为，只要深入理解了求背包问题最大价值的方法，即使问法变化了，也是不难想出算法的。

输出方案

一般而言，背包问题是要求一个最优值，如果要求输出这个最优值的方案，可以参照一般动态规划问题输出方案的方法：记录下每个状态的最优值是由状态转移方程的哪一项推出来的，换句话说，记录下它是由哪一个策略推出来的。便可根据这条策略找到上一个状态，从上一个状态接着向前推即可。

还是以01背包为例，方程为f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}。再用一个数组g[i][v]，设g[i][v]=0表示推出f[i][v]的值时是采用了方程的前一项（也即f[i][v]=f[i-1][v]），g[i][v]表示采用了方程的后一项。注意这两项分别表示了两种策略：未选第i个物品及选了第i个物品。

输出字典序最小的最优方案

这里“字典序最小”的意思是1...N号物品的选择方案排列出来以后字典序最小。以输出01背包最小字典序的方案为例。

一般而言，求一个字典序最小的最优方案，只需要在转移时注意策略。首先，子问题的定义要略改一些。我们注意到，如果存在一个选了物品1的最优方案，那么答案一定包含物品1，原问题转化为一个背包容量为v-c[1]，物品为2..N的子问题。反之，如果答案不包含物品1，则转化成背包容量仍为V，物品为2..N的子问题。不管答案怎样，子问题的物品都是以i..N而非前所述的1..i的形式来定义的，所以状态的定义和转移方程都需要改一下。但也许更简易的方法是先把物品逆序排列一下，以下按物品已被逆序排列来叙述。

在这种情况下，可以按照前面经典的状态转移方程来求值，只是输出方案的时候要注意：从N到1输入时，如果f[i][v]==f[i-1][i-v]及f[i][v]==f[i-1][f-c[i]]+w[i]同时成立，应该按照后者（即选择了物品i）来输出方案。

典型例题

输出字典序最小的最优方案

题目要求输出字典序最小的解，假设存在一个包含第1个物品的最优解，为了确保字典序最小那么我们必然要选第一个。那么问题就转化成从2～N这些物品中找到最优解。

之前的f(i,j) 记录的都是前i 个物品总容量为j 的最优解，那么我们现在将f(i,j) 定义为从第i 个元素到最后一个元素总容量为j 的最优解。

接下来考虑状态转移：

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

两种情况，第一种是不选第i 个物品，那么最优解等同于从第i+1 个物品到最后一个元素总容量为j 的最优解；第二种是选了第i 个物品，那么最优解等于当前物品的价值w[i] 加上从第i+1 个物品到最后一个元素总容量为j−v[i] 的最优解。

计算完状态表示后，考虑如何的到最小字典序的解。首先f(1,m) 肯定是最大价值，那么我们便开始考虑能否选取第1个物品呢。

• 如果f(1,m)=f(2,m−v[1])+w[1] ，说明选取了第1个物品可以得到最优解。
• 如果f(1,m)=f(2,m) ，说明不选取第一个物品才能得到最优解。
• 如果f(1,m)=f(2,m)=f(2,m−v[1])+w[1] ，说明选不选都可以得到最优解，但是为了考虑字典序最小，我们也需要选取该物品。

int N, V;
int arrV[1005];
int arrW[1005];
int dp[1005][1005];

int main() {
    cin >> N >> V;
    memset(dp, 0, sizeof(dp));
    memset(arrV, 0, sizeof(arrV));
    memset(arrW, 0, sizeof(arrW));
    for (int i = 1; i <= N; i++) {
        cin >> arrV[i] >> arrW[i];
    }
    for (int i = N; i >= 1; i--) {
        for (int j = 0; j <= V; j++) {
            dp[i][j] = dp[i + 1][j];
            if (j >= arrV[i])
                dp[i][j] = max(dp[i][j], dp[i + 1][j - arrV[i]] + arrW[i]);
        }
    }
    int curV = V;
    for (int i = 1; i <= N; i++) {
        if (curV - arrV[i] >= 0 && dp[i][curV] == dp[i + 1][curV - arrV[i]] + arrW[i]) {
            cout << i << " ";
            curV -= arrV[i];
        }
    }
}

求方案总数

对于一个给定了背包容量、物品费用、物品间相互关系（分组、依赖等）的背包问题，除了再给定每个物品的价值后求可得到的最大价值外，还可以得到装满背包或将背包装至某一指定容量的方案总数。

对于这类改变问法的问题，一般只需将状态转移方程中的max改成sum即可。

例如若每件物品均是完全背包中的物品，转移方程即为f[i][v] = sum{f[i − 1][v], f[i][v − c[i]]}。初始条件f[0][0]=1。

事实上，这样做可行的原因在于状态转移方程已经考察了所有可能的背包组成方案。

最优方案的总数

这里的最优方案是指物品总价值最大的方案。以01背包为例。

结合求最大总价值和方案总数两个问题的思路，最优方案的总数可以这样求：f[i][v]意义同前述，g[i][v]表示这个子问题的最优方案的总数，则在求f[i][v]的同时求g[i][v]的伪代码如下：

1 for i ← 1 to N
2 do for v ← 0 to V
3 do f[i][v] = max{f[i − 1][v], f[i − 1][v − c[i]] + w[i]}
4 g[i][v] = 0
5 if (f[i][v] = f[i − 1][v])
6 then g[i][v] ← g[i][v] + g[i − 1][v]
7 if f[i][v] = f[i − 1][v − c[i]] + w[i]
8 then g[i][v] ← g[i][v] + g[i − 1][v − c[i]]

如果你是第一次看到这样的问题，请仔细体会上面的伪代码。

典型例题

背包问题求方案数

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。第 i 件物品的体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。

输出 最优选法的方案数。注意答案可能很大，请输出答案模 10^9+7 的结果。

constexpr int p = 1e9 + 7;
int N, V;
int dp[1005][1005];
long long ans[1005][1005];

int main() {
    cin >> N >> V;
    memset(dp, 0, sizeof(dp));
    memset(ans, 0, sizeof(ans));
    for (int i = 0; i <= V; i++) ans[0][i] = 1;
    for (int i = 1; i <= N; i++) {
        int v, w;
        cin >> v >> w;
        for (int j = 0; j <= V; j++) {
            dp[i][j] = dp[i - 1][j];
            ans[i][j] = ans[i - 1][j];
            if (j >= v) {
                if (dp[i][j] < dp[i - 1][j - v] + w) {
                    dp[i][j] = dp[i - 1][j - v] + w;
                    ans[i][j] = ans[i - 1][j - v];
                } else if (dp[i][j] == dp[i - 1][j - v] + w) {
                    ans[i][j] =  (ans[i][j] + ans[i - 1][j - v]) % p;
                }
            }
        }
    }
    cout << ans[N][V] << endl;
}

求次优解、第K优解

对于求次优解、第K优解类的问题，如果相应的最优解问题能写出状态转移方程、用动态规划解决，那么求次优解往往可以相同的复杂度解决，第K优解则比求最优解的复杂度上多一个系数K。

其基本思想是将每个状态都表示成有序队列，将状态转移方程中的max/min转化成有序队列的合并。这里仍然以01背包为例讲解一下。

首先看01背包求最优解的状态转移方程：f[i][v] = max{f[i − 1][v], f[i − 1][v − c[i]] + w[i]}。

如果要求第K优解，那么状态f[i][v]就应该是一个大小为K的数组f[i][v][1..K]。其中f[i][v][k]表示前i个物品、背包大小为v时，第k优解的值。“f[i][v]是一个大小为K的数组”这一句，熟悉C语言的同学可能比较好理解，或者也可以简单地理解为在原来的方程中加了一维。

显然f[i][v][1..K]这K个数是由大到小排列的，所以我们把它认为是一个有序队列。

然后原方程就可以解释为：f[i][v]这个有序队列是由f[i-1][v]和f[i-1][v-c[i]]+w[i]这两个有序队列合并得到的。

有序队列f[i-1][v]即f[i-1][v][1..K]，f[i-1][v-c[i]]+w[i]则理解为在f[i-1][v-c[i]][1..K]的每个数上加上w[i]后得到的有序队列。合并这两个有序队列并将结果的前K项储存到f[i][v][1..K]中的复杂度是O(K)。最后的答案是f[N][V][K]。总的复杂度是Θ(VNK)。

为什么这个方法正确呢？实际上，一个正确的状态转移方程的求解过程遍历了所有可用的策略，也就覆盖了问题的所有方案。只不过由于是求最优解，所以其它在任何一个策略上达不到最优的方案都被忽略了。如果把每个状态表示成一个大小为K的数组，并在这个数组中有序的保存该状态可取到的前K个最优值。

那么，对于任两个状态的max运算等价于两个由大到小的有序队列的合并。另外还要注意题目对于“第K优解”的定义，将策略不同但权值相同的两个方案是看作同一个解还是不同的解。如果是前者，则维护有序队列时要保证队列里的数没有重复的。

典型例题

Bone Collector II

int arrV[105];
int arrW[105];
int tempA[35];
int tempB[35];
int dp[1005][35];

int main() {
    int t;
    cin >> t;
    while (t--) {
        int N, V, K;
        memset(dp, 0, sizeof(dp));
        cin >> N >> V >> K;
        for (int i = 1; i <= N; i++)
            cin >> arrW[i];
        for (int i = 1; i <= N; i++)
            cin >> arrV[i];
        for (int i = 1; i <= N; i++) {
            for (int j = V; j >= arrV[i]; j--) {
                for (int k = 1; k <= K; k++) {
                    tempA[k] = dp[j - arrV[i]][k] + arrW[i];
                    tempB[k] = dp[j][k];
                    if (k == K) tempA[k + 1] = -1, tempB[k + 1] = -1;
                }
                int x, y, z;
                x = y = z = 1;
                while (z <= K && (tempA[x] != -1 || tempB[y] != -1)) {
                    if (tempA[x] > tempB[y])
                        dp[j][z] = tempA[x++];
                    else dp[j][z] = tempB[y++];
                    if (dp[j][z] != dp[j][z - 1]) z++;
                }
            }
        }
        cout << dp[V][K] << endl;
    }
}