背包问题中的动态规划思想

zhyjc6于2020-09-14发布 约19603字·约43分钟 本文总阅读量次

0. 动态规划

概念

动态规划（英语：Dynamic programming，简称DP）是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

动态规划在查找有很多重叠子问题的情况的最优解时有效。它将问题重新组合成子问题。为了避免多次解决这些子问题，它们的结果都逐渐被计算并被保存，从简单的问题直到整个问题都被解决。因此，动态规划保存递归时的结果，因而不会在解决同样的问题时花费时间。

动态规划只能应用于有最优子结构的问题。最优子结构的意思是局部最优解能决定全局最优解（对有些问题这个要求并不能完全满足，故有时需要引入一定的近似）。简单地说，问题能够分解成子问题来解决。

基本思想

动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再根据子问题的解以得出原问题的解。

通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量：一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。

动态规划与分治法相似，都是通过组合子问题的解来求解原问题。它们不同之处在于，分治法将问题划分为互不相交的子问题，递归地求解子问题，再将它们的解组合起来，求出原问题的解。而与之相反，动态规划应用于子问题重叠的情况，即不同的子问题具有公共的子子问题（子问题的求解是递归进行的，将其划分为更小的子子问题）。在这种情况下，分治法会做许多不必要的工作，它会反复地求解那些公共子子问题，而动态规划算法对每个子子问题只求解一次，将其解保存在一个表格中，从而无需每次求解一个子子问题时都重新计算，避免了这种不必要的计算工作。

适用情况

  1. 最优子结构性质。如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质（即满足最优化原理）。最优子结构性质为动态规划算法解决问题提供了重要线索。
  2. 无后效性。即子问题的解一旦确定，就不再改变，不受在这之后、包含它的更大的问题的求解决策影响。
  3. 子问题重叠性质。子问题重叠性质是指在用递归算法自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存在一个表格中，当再次需要计算已经计算过的子问题时，只是在表格中简单地查看一下结果，从而获得较高的效率，降低了时间复杂度。

1. 01背包

题目描述

题目链接

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

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

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

输入格式

第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。

接下来有 N 行，每行两个整数 vi，wi，用空格隔开，分别表示第 i 件物品的体积和价值。

输出格式

输出一个整数，表示最大价值。

输入样例

4 5
1 2
2 4
3 4
4 5

输出样例

8

代码实现

实现1：朴素动态规划

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int N, V;
    cin >> N >> V;
    vector<int> v(N), w(N);
    for (int i = 0; i < N; ++i) {
        cin >> v[i] >> w[i]; //体积和价值
    }
    vector<vector<int>> dp(N+1, vector<int>(V+1, 0));
    for (int i = 1; i <= N; ++i) {
        for (int j = 0; j <= V; ++j) {
            dp[i][j] = dp[i-1][j]; //没得选择
            if (j >= v[i-1])
                //            不要第i个物品      要第i个物品
                dp[i][j] = max(dp[i][j], dp[i-1][j-v[i-1]] + w[i-1]);   
        }
    }

    cout << dp[N][V] << endl;
    return 0;
}

实现2：空间优化

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int N, V;
    cin >> N >> V;
    vector<int> v(N+1), w(N+1);
    for (int i = 1; i <= N; ++i) {
        cin >> v[i] >> w[i]; //体积和价值
    }
    vector<int> dp(V+1, 0);
    for (int i = 1; i <= N; ++i) {
        for (int j = V; j >= v[i]; --j) { //这里为什么要逆序？？？后面会说明。
            dp[j] = max(dp[j], dp[j-v[i]]+w[i]);
        }
    }
    cout << dp[V] << endl;
    return 0;
}

初始化的细节问题

我们看到的求最优解的背包问题题目中，事实上有两种不太相同的问法。有的题目要求“恰好装满背包”时的最优解，有的题目则并没有要求必须把背包装满。一种区别 这两种问法的实现方法是在初始化的时候有所不同。

如果是第一种问法，要求恰好装满背包，那么在初始化时除了 F[0] 为 0，其它 F[1..V ] 均设为 −∞，这样就可以保证最终得到的 F[V ] 是一种恰好装满背包的最优解。 如果并没有要求必须把背包装满，而是只希望价格尽量大，初始化时应该将 F[0..V ] 全部设为 0。

这是为什么呢？可以这样理解：初始化的 F 数组事实上就是在没有任何物品可以放 入背包时的合法状态。如果要求背包恰好装满，那么此时只有容量为 0 的背包可以在什么也不装且价值为 0 的情况下被“恰好装满”，其它容量的背包均没有合法的解，属于 未定义的状态，应该被赋值为 -∞ 了。如果背包并非必须被装满，那么任何容量的背包 都有一个合法解“什么都不装”，这个解的价值为 0，所以初始时状态的值也就全部为 0 了。 这个小技巧完全可以推广到其它类型的背包问题，后面不再对进行状态转移之前的 初始化进行讲解。

2. 完全背包问题

题目描述

题目链接

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

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

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

输入格式

第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。

接下来有 N 行，每行两个整数 vi，wi，用空格隔开，分别表示第 i 种物品的体积和价值。

输出格式

输出一个整数，表示最大价值。

输入样例

4 5
1 2
2 4
3 4
4 5

输出样例

10

代码实现

实现1：朴素动态规划

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int N, V;
    cin >> N >> V;
    vector<int> v(N+1), w(N+1);
    for (int i = 1; i <= N; ++i) {
        cin >> v[i] >> w[i]; //体积和价值
    }
    vector<vector<int>> dp(N+1, vector<int>(V+1, 0)); //dp[i][j]表示在背包体积为j的情况下，只装前i种物品得到的最大价值
    for (int i = 1; i <= N; ++i) {
        for (int j = 0; j <= V; ++j)  {
            int maxValue = 0;
            for (int k = 0; k*v[i] <= j; ++k) { //当前物品取k件，看看哪次得到的结果最大
                maxValue = max(maxValue, dp[i-1][j-k*v[i]] + k*w[i]);
            }
            dp[i][j] = maxValue;
        }
    }
    cout << dp[N][V] << endl;
    return 0;
}

实现2：优化第3重循环

我们需要的dp[i][j]的状态表示是：
dp[i][j]= max(dp[i-1][j], dp[i-1][j-v]+w, dp[i-1][j-2*v]+2*w, dp[i-1][j-3*v]+3*w, ......);
而dp[i][j-v]的状态表示是：
dp[i][j-v] = max(dp[i-1][j-v], dp[i-1][j-2*v] + w, dp[i-1][j-3*v] + 2*w, .....);
将每一项一一比对，我们可以得到下列状态表示:
dp[i][j] = max(dp[i-1][j], dp[i][j-v]+w);

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int N, V;
    cin >> N >> V;
    vector<int> v(N+1), w(N+1);
    for (int i = 1; i <= N; ++i) {
        cin >> v[i] >> w[i]; //体积和价值
    }
    vector<vector<int>> dp(N+1, vector<int>(V+1, 0)); //dp[i][j]表示在背包体积为j的情况下，只装前i种物品得到的最大价值
    for (int i = 1; i <= N; ++i) {
        for (int j = 0; j <= V; ++j)  {
            dp[i][j] = dp[i-1][j];
            if (j >= v[i]) //确保j-v[i] >= 0
                dp[i][j] = max(dp[i-1][j], dp[i][j-v[i]] + w[i]);
        }
    }
    cout << dp[N][V] << endl;
    return 0;
}

实现3：滚动数组优化

由于二维数组dp当前位置只依赖第一维度的上一轮的值，我们可以将第一个维度直接&1，那么数据就会保存在dp[0][x]和dp[1][x]中。只要用到dp[2][N]这么大的数组就足够了。

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int N, V;
    cin >> N >> V;
    vector<int> v(N+1), w(N+1);
    for (int i = 1; i <= N; ++i) {
        cin >> v[i] >> w[i]; //体积和价值
    }
    vector<vector<int>> dp(2, vector<int>(V+1, 0)); //dp[i][j]表示在背包体积为j的情况下，只装前2k+i种物品得到的最大价值
    for (int i = 1; i <= N; ++i) {
        for (int j = 0; j <= V; ++j)  {
            dp[i&1][j] = dp[(i-1)&1][j];
            if (j >= v[i])
                dp[i&1][j] = max(dp[(i-1)&1][j], dp[i&1][j-v[i]] + w[i]);
        }
    }
    cout << dp[N&1][V] << endl;
    return 0;
}

实现4：一维数组优化

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int N, V;
    cin >> N >> V;
    vector<int> v(N+1), w(N+1);
    vector<int> dp(V+1, 0);
    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 <= V; ++j) { //为什么这里要顺序？？？后面会说明
            dp[j] = max(dp[j], dp[j-v[i]]+w[i]);
        }
    }
    cout << dp[V] << endl;
    return 0;
}

一维优化的细节问题

我们发现，完全背包与 01 背包问题的代码只有 v 的循环次序不同而已。

为什么同样是一维优化，01背包的遍历是逆序遍历，而完全背包则是顺序遍历？

首先想想为什么 01 背包中要按照 v 递减的次序来循环。 让 v 递减是为了保证第 i 次循环中的状态 dp[i,v] 是由状态 dp[i−1,v −vi] 递推而来。 换句话说，这正是为了保证每件物品只选一次，保证在考虑“选入第 i 件物品”这个策略时，依据的是一个绝对没有选入第 i 件物品的子结果 dp[i−1,v−vi]。而现在完全背包的特点恰是每种物品可选无限件，所以在考虑“加选一件第 i 种物品”这种策略时， 却正需要一个可能已选入第 i 种物品的子结果 dp[i,v−vi]，所以就可以并且必须采用 v 递增的顺序循环。

3. 多重背包问题

题目描述

题目链接

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

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

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

输入格式

第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。

接下来有 N 行，每行三个整数 vi，wi，si，用空格隔开，分别表示第 i 种物品的体积、价值和数量。

输出格式

输出一个整数，表示最大价值。

输入样例

4 5
1 2 3
2 4 1
3 4 3
4 5 2

输出样例：

10

代码实现

实现1：朴素动态规划

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int N, V;
    cin >> N >> V;
    vector<int> v(N+1), w(N+1), s(N+1);
    for (int i = 1; i <= N; ++i) {
        cin >> v[i] >> w[i] >> s[i]; //体积、价值和数量
    }
    vector<vector<int>> dp(N+1, vector<int>(V+1, 0)); //dp[i][j]表示在背包体积为j的情况下，只装前i种物品得到的最大价值
    for (int i = 1; i <= N; ++i) {
        for (int j = 0; j <= V; ++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][V] << endl;
    return 0;
}

实现2：优化为一维空间

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int N, V;
    cin >> N >> V;
    vector<int> v(N+1), w(N+1), s(N+1);
    for (int i = 1; i <= N; ++i) {
        cin >> v[i] >> w[i] >> s[i]; //体积、价值和数量
    }
    vector<int> dp(V+1, 0); //dp[j]表示在背包体积为j的情况下，只装前i种(第i轮)物品得到的最大价值
    for (int i = 1; i <= N; ++i) {
        for (int j = V; j >= v[i]; --j)  { //有空间压缩就要反向遍历
            for (int k = 0; k <= s[i] && k*v[i] <= j; ++k) {
                dp[j] = max(dp[j], dp[j-k*v[i]] + k*w[i]);
            }
        }
    }
    cout << dp[V] << endl;
    return 0;
}

实现3：二进制优化

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int N, V;
    int a, b, c;
    cin >> N >> V;
    vector<int> v, w;
    for (int i = 0; i < N; ++i) {
        cin >> a >> b >> c; //体积、价值和数量
        for (int k = 1; k <= c; k *= 2) { //将其化为01背包问题
            v.push_back(k*a); //10 = 1 + 2 + 4 + 3
            w.push_back(k*b); //19 = 1 + 2 + 4 + 8 + 4
            c -= k;
        }
        if (c != 0) {
            v.push_back(c*a);
            w.push_back(c*b);
        }

    }
    vector<int> dp(V+1, 0);//dp[j]表示在背包体积为j的情况下，只装前i种(第i轮)物品得到的最大价值
    for (int i = 0; i < v.size(); ++i) { //记住这里for循环的次数是数组v的大小，不是N，多重背包转化为01背包，物品数量变多了
        for (int j = V; j >= v[i]; --j) { //既然压缩了空间又是01背包，这里就需要逆序遍历
            dp[j] = max(dp[j], dp[j-v[i]] + w[i]);
        }
    }
    cout << dp[V] << endl;
    return 0;
}

实现4：单调队列

这里不单独讨论单调队列，需要练习单调队列可以看看leetcode上的这道题 leetcode239

我们先看一下传统的朴素的转移方程：
dp[i][j] = max(dp[i-1][j], dp[i-1][j-v] + w, dp[i-1][j-2*v] + 2*w,..., dp[i-1][j-k*v] + k*w)

实际上我们并不需要二维的dp数组，适当的调整循环条件，我们可以重复利用dp数组来保存上一轮的信息
我们令 dp[j] 表示容量为j的情况下，获得的最大价值
那么，针对每一类物品 i ，我们都更新一下 dp[m] --> dp[0] 的值，最后 dp[m] 就是一个全局最优值
dp[m] = max(dp[m], dp[m-v] + w, dp[m-2*v] + 2*w, dp[m-3*v] + 3*w, ...)

接下来，我们把 dp[0] --> dp[m] 写成下面这种形式（j表示当前物品体积v的余数，即0~v-1）
dp[0], dp[v],   dp[2*v],   dp[3*v],   ... , dp[k*v]
dp[1], dp[v+1], dp[2*v+1], dp[3*v+1], ... , dp[k*v+1]
dp[2], dp[v+2], dp[2*v+2], dp[3*v+2], ... , dp[k*v+2]
...
dp[j], dp[v+j], dp[2*v+j], dp[3*v+j], ... , dp[k*v+j]
显而易见，m 一定等于 k*v + j，因为j = m % v。

由于dp[k*v+j] 只依赖于 { dp[j], dp[v+j], dp[2*v+j], dp[3*v+j], ... , dp[k*v+j] }
那么我们就可以依据v的余数j将dp[0~m]这m+1个问题分成j+1组，每组之间的结果互不影响

那为什么每组之间互不影响，我们仍然要将每一组都求出呢？
这是因为当前的分组我们是按照当前物品体积大小进行的分组，下一个物品体积不同时，分组就会错开。
所以必须将每个分组都求出来。比如说dp[0~10],可能第一个物品分组如下：
dp[0], dp[2], dp[4], dp[6], dp[8]
dp[1], dp[3], dp[5], dp[7], dp[9]
而第二个个物品的分组就是这个样子：
dp[0], dp[3], dp[6], dp[9]
dp[1], dp[4], dp[7],
dp[2], dp[5], dp[8],
这样在第二轮中原来第一轮的不同分组的可能变成了一组，也就是互相影响。

那我们如何通过O(1)的时间得到dp[m] = max(dp[m], dp[m-v] + w, dp[m-2*v] + 2*w, dp[m-3*v] + 3*w, ...)的结果呢？
答案是通过单调队列
可以通过维护一个单调队列来得到结果。这样的话，问题就变成了 j 个单调队列的问题

所以，我们可以得到
dp[j]    =     dp[j]
dp[j+v]  = max(dp[j] +  w,  dp[j+v])
dp[j+2v] = max(dp[j] + 2w,  dp[j+v] +  w, dp[j+2v])
dp[j+3v] = max(dp[j] + 3w,  dp[j+v] + 2w, dp[j+2v] + w, dp[j+3v])
...
但是，这个队列中前面的数，每次都会增加一个 w ，所以我们需要做一些转换：
dp[j]    =     dp[j]
dp[j+v]  = max(dp[j], dp[j+v] - w) + w
dp[j+2v] = max(dp[j], dp[j+v] - w, dp[j+2v] - 2w) + 2w
dp[j+3v] = max(dp[j], dp[j+v] - w, dp[j+2v] - 2w, dp[j+3v] - 3w) + 3w
...
这样，每次入队的值是 dp[j+k*v] - k*w

单调队列问题，最重要的两点
1）维护队列元素的个数，如果不能继续入队，弹出队头元素
2）维护队列的单调性，即：尾值 >= dp[j + k*v] - k*w，队列从头到尾是单调递减的

注意这里说的单调队列中元素个数并不是真正的元素个数，而是元素范围。
因为单调队列中存储的是当前物品可以存放的个数k，并且k是递增遍历的，
所以队列首部的k一定是最小的，尾部的k一定是最大的，他们之差就是这个队列中k的范围
根据题目的意思，这个范围一定不能超过当前物品的数量s。
因为dp[j+kv]表示背包容积为j+kv时，所能获取的最大价值。其决策有s+1种，即当前物品选择0~s次。

代码：

#include <iostream>
#include <cstring>

using namespace std;

const int MAX_SIZE = 20010;

int dp[MAX_SIZE], pre[MAX_SIZE], q[MAX_SIZE];
int N, V;
//因为我们不是顺序求出dp[V]的，所以我们需要一个辅助数组pre[V]来保存前一轮的结果
//单调队列中保存的是每个物品的数量，
//对于每一种物品，我们都可以取0，1，2，，，k种，而这其中的最大结果的k值就保存在队列首部
int main() {
    cin >> N >> V; //物品种类为N，背包容量为V
    for (int i = 0; i < N; ++i) { //依次遍历每一种物品
        memcpy(pre, dp, sizeof(dp)); //保存前一轮的结果
        int v, w, s;
        cin >> v >> w >> s; //获取当前物品的体积、价值、数量
        for (int j = 0; j < v; ++j) { //将dp[0~V]按照v的余数分成v组
            int head = 0, tail = -1; //初始化单调队列
            for (int k = 0; j+k*v <= V; ++k) { //当前物品我们可以取k个（j+k*v<=V）
                //队列中物品使用次数可能超过物品的数量s
                if (head <= tail && k-q[head] > s) //这时候就将队首弹出
                    ++head;

                //移除单调队列尾部小于当前元素的所有元素
                while (head <= tail && pre[j+k*v] - k*w >= pre[j+q[tail]*v] - q[tail]*w) {
                    --tail;
                }
                q[++tail] = k; //加入队列
                dp[j+k*v] = pre[j+q[head]*v] - q[head]*w + k*w; //获取队列首部的k对应的价值
            }
        }
    }
    cout << dp[V] << endl;
    return 0;
}

滚动数组：

#include <iostream>
#include <vector>

using namespace std;
int q[20005];
int main() {
    int N, V;
    cin >> N >> V;
    vector<int> v(N+1), w(N+1), s(N+1);
    for (int i = 1; i <= N; ++i) {
        cin >> v[i] >> w[i] >> s[i];
    }
    vector<vector<int>> dp(2, vector<int>(V+1, 0));
    for (int i = 1; i <= N; ++i) {
        for (int j = 0; j < v[i]; ++j) {
            int head = 0, tail = -1;
            for (int k = 0; j+k*v[i] <= V; ++k) {
                if (head <= tail && k - q[head] > s[i]) head++;
                while (head <= tail && dp[(i-1)&1][j+q[tail]*v[i]] - q[tail]*w[i] <= dp[(i-1)&1][j+k*v[i]] - k*w[i]) --tail;
                q[++tail] = k;
                dp[i&1][j+k*v[i]] = dp[(i-1)&1][j+q[head]*v[i]] - q[head]*w[i] + k*w[i];
            }
        }
    }
    cout << dp[N&1][V] << endl;
    return 0;
}

4. 混合背包问题

题目描述

题目链接

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

物品一共有三类：

  • 第一类物品只能用1次（01背包）；
  • 第二类物品可以用无限次（完全背包）；
  • 第三类物品最多只能用 si 次（多重背包）；

每种体积是 vi，价值是 wi。

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

输入格式

第一行两个整数，N，V 用空格隔开，分别表示物品种数和背包容积。

接下来有 N 行，每行三个整数 vi，wi，si，用空格隔开，分别表示第 i 种物品的体积、价值和数量。

  • si = −1 表示第 i 种物品只能用1次；
  • si = 0 表示第 i 种物品可以用无限次；
  • si > 0 表示第 i 种物品可以使用 si 次；

输出格式

输出一个整数，表示最大价值。

输入样例

4 5
1 2 -1
2 4 1
3 4 0
4 5 2

输出样例

8

代码实现

实现1：多重背包转化为01背包

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
struct thing {
    int kind; //-1表示01背包；0表示完全背包
    int v, w; //体积和价值
};

int main() {
    int N, V;
    vector<thing> things;
    cin >> N >> V; //物品数量和背包容量
    int v, w, s; //物品体积、价值、数量

    for (int i = 0; i < N; ++i) {
        cin >> v >> w >> s;
        if (s == -1) { //01背包
        things.push_back({-1, v, w});
        } else if (s == 0) { //完全背包
            things.push_back({0, v, w});
        } else if (s > 0) { //多重背包->使用二进制思想转化为01背包
            for (int k = 1; k < s; k *= 2) {
                s -= k;
                things.push_back({-1, k*v, k*w});
            }
            things.push_back({-1, s*v, s*w});
        }
    }
    
    vector<int> dp(V+1, 0);
    for (auto cur : things) { //一一遍历每个物品，对于当前物品，分别处理完全背包和01背包
        if (cur.kind == 0) { //完全背包
            for (int j = cur.v; j <= V; ++j) {
                dp[j] = max(dp[j], dp[j-cur.v]+cur.w);
            }
        } else if (cur.kind == -1) { //01背包
            for (int j = V; j >= cur.v; --j) {
                dp[j] = max(dp[j], dp[j-cur.v]+cur.w);
            }
        }
    }

    cout << dp[V] << endl;
    return 0;
}

5. 二维费用背包问题

题目描述

题目链接

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

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

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

输入格式

第一行两个整数，N，V，M，用空格隔开，分别表示物品件数、背包容积和背包可承受的最大重量。

接下来有 N 行，每行三个整数 vi，mi，wi，用空格隔开，分别表示第 i 件物品的体积、重量和价值。

输出格式

输出一个整数，表示最大价值。

输入样例

4 5 6
1 2 3
2 4 4
3 4 5
4 5 6

输出样例

8

代码实现

费用加了一维，只需状态也加一维即可。设 F[i,v,u] 表示当背包容量为v、可承受重量为u时，取前 i 种物品可获得的最大价值。状态转移方程就是： F[i,v,u] = max{F[i−1,v,u]，F[i−1,v−vi,u−ui] +wi}

实现1：朴素动态规划

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
    int N, V, M;
    cin >> N >> V >> M; //物品数量 背包容量 背包可承受最大重量
    vector<vector<vector<int>>> dp(N+1, vector<vector<int>>(V+1, vector<int>(M+1, 0)));
    vector<int> v(N+1), m(N+1), w(N+1); //物品的体积 重量 价值
    for (int i = 1; i <= N; ++i) {
        cin >> v[i] >> m[i] >> w[i];
    }
    for (int i = 1; i <= N; ++i) {
        for (int j = 0; j <= V; ++j) {
            for (int k = 0; k <= M; ++k) {
                if (j < v[i] || k < m[i]) {
                    dp[i][j][k] = dp[i-1][j][k];
                } else {
                    dp[i][j][k] = max(dp[i-1][j][k], dp[i-1][j-v[i]][k-m[i]] + w[i]);
                }
            }
        }
    }
    
    cout << dp[N][V][M] << endl;
    
    return 0;
}

实现2：二维空间优化

如前述优化空间复杂度的方法，可以只使用二维的数组：当每件物品只可以取一次时 体积和重量 采用逆序的循环，当物品有如完全背包问题时采用顺序的循环，当物品 有如多重背包问题时拆分物品。

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
    int N, V, M;
    cin >> N >> V >> M; //物品数量 背包容量 背包可承受最大重量
    vector<vector<int>> dp(V+1, vector<int>(M+1, 0));
    vector<int> v(N+1), m(N+1), w(N+1); //物品的体积 重量 价值
    for (int i = 1; i <= N; ++i) {
        cin >> v[i] >> m[i] >> w[i];
    }
    for (int i = 1; i <= N; ++i) {
        for (int j = V; j >= v[i]; --j) {
            for (int k = M; k >= m[i]; --k) {
                dp[j][k] = max(dp[j][k], dp[j-v[i]][k-m[i]] + w[i]);
            }
        }
    }
    
    cout << dp[V][M] << endl;
    
    return 0;
}

6. 分组背包

题目描述

题目链接

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

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

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

输入格式

第一行有两个整数 N，V，用空格隔开，分别表示物品组数和背包容量。

接下来有 N 组数据：

  • 每组数据第一行有一个整数 Si，表示第 i 个物品组的物品数量；
  • 每组数据接下来有 Si 行，每行有两个整数 vij，wij，用空格隔开，分别表示第 i 个物品组的第 j 个物品的体积和价值；

输出格式

输出一个整数，表示最大价值。

输入样例

3 5
2
1 2
2 4
1
3 4
1
4 5

输出样例

8

代码实现

这个问题变成了每组物品有若干种策略：是选择本组的某一件，还是一件都不选。 也就是说设 F[k,v] 表示前 k 组物品花费费用 v 能取得的最大价值，则有： F[k,v] = max{F[k−1,v]，F[k−1,v−vi] + wi itemi ∈group k}

实现1：朴素动态规划

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
    int N, V;
    cin >> N >> V; //物品组数 背包容量
    int count; //一组物品数量

    vector<vector<int>> dp(N+1, vector<int>(V+1, 0));
    for (int i = 1; i <= N; ++i) { //对于每一组物品
        cin >> count;
        vector<int> v(count), w(count);
        for (int j = 0; j < count; ++j) {
            cin >> v[j] >> w[j];
        }
        for (int j = 1; j <= V; ++j) { //对于每种体积
            int tempMax = 0;  //记录每种决策的最大值
            dp[i][j] = dp[i-1][j]; //不选
            for (int k = 0; k < count; ++k) { //从count个物品中选一种
                if (j >= v[k]) {
                    dp[i][j] = max(dp[i][j], dp[i-1][j-v[k]] + w[k]);
                }
            }
        }
    }
    
    cout << dp[N][V] << endl;
    
    return 0;
}

实现2：一维空间优化

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
    int N, V;
    cin >> N >> V; //物品组数 背包容量
    int count; //一组物品数量
    int v, w; //物品体积和价值
    vector<int> dp(V+1, 0);
    for (int i = 0; i < N; ++i) { //对于每一组物品
        cin >> count;
        vector<int> v(count+1), w(count+1);
        for (int i = 1; i <= count; ++i) {
            cin >> v[i] >> w[i];
        }
        for (int j = V; j >= 0; --j) { //对于每一种体积
            for (int k = 1; k <= count; ++k) { //遍历每一种决策
                if (j >= v[k]) { //不选当前组中物品还是选择其中一件，选择哪一件
                    dp[j] = max(dp[j], dp[j-v[k]]+w[k]);
                }
            }
        }
    }
    
    cout << dp[V] << endl;
    
    return 0;
}

这里三层循环的顺序保证了每一组内的物品最多只有一个会被添加到背包中。

7. 有依赖的背包问题

题目描述

题目链接

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

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

如下图所示：

1_bb51ecbcd2-QQ图片20181018170337

如果选择物品5，则必须选择物品1和2。这是因为2是5的父节点，1是2的父节点。

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

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

输入格式

第一行有两个整数 N，V，用空格隔开，分别表示物品个数和背包容量。

接下来有 N 行数据，每行数据表示一个物品。第 i 行有三个整数 vi，wi，pi，用空格隔开，分别表示物品的体积、价值和依赖的物品编号。如果 pi = −1，表示根节点。 数据保证所有物品构成一棵树。

输出格式

输出一个整数，表示最大价值。

输入样例

5 7
2 3 -1
2 2 1
3 5 1
4 7 2
3 6 2

输出样例

11

代码实现

实现1

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
const int H = 110;
int N, V, root;
int dp[H][H]; //因为依赖关系是必须选择父节点，所以这里我们dp[i][j]就默认在容积为j的情况下，一定选择结点i所能获得的最大价值
int v[H], w[H];
vector<int> child[H]; //采用类似邻接链表的方式存储直属子结点

void dfs(int p);

int main() {
    cin >> N >> V; //物品个数 背包容量
    int p;
    for (int i = 1; i <= N; ++i) {
        cin >> v[i] >> w[i] >> p;
        if (p == -1) { //p=-1,i就是根结点
            root = i;
        } else { //否则，i的父节点就是p
            child[p].push_back(i);
        }
    }
    dfs(root);
    cout << dp[root][V] << endl; //无论怎么选，都一定会选到根结点
    return 0;
}

void dfs(int parent) {
    for (int j = v[parent]; j <= V; ++j) {
        dp[parent][j] = w[parent]; //对于大于当前物品体积的体积，先把当前结点选上
    }
    for (int i = 0; i < child[parent].size(); ++i) { //再一一处理root的每一个直系子结点
        int son = child[parent][i];
        dfs(son); //递归处理，这样就是自底向上，这行以下就代表son结点已经被递归函数处理好了
        for (int j = V; j >= v[parent]; --j) { //对于小于当前物品体积的容积，因为一定要选择当前物品但又装不下，所以dp[parent][j] = 0
            for (int k = 0; k <= j-v[parent]; ++k) { //k表示留给子树的容积空间
                dp[parent][j] = max(dp[parent][j], dp[parent][j-k] + dp[son][k]);
            }
        }
    }
}

8. 背包问题求方案数

题目描述

题目链接

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

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

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

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

输入格式

第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。

接下来有 N 行，每行两个整数 vi，wi，用空格隔开，分别表示第 i 件物品的体积和价值。

输出格式

输出一个整数，表示 方案数 模 $10^9+7$ 的结果。

输入样例

4 5
1 2
2 4
3 4
4 6

输出样例

2

代码实现

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

const int mod = 1000000000 + 7, inf = 1000000000;
int dp[1010]; //dp[i]表示体积为i并且恰好装满背包所能得到的最大价值（不同于之前，因此要注意初始化的问题）
int cnt[1010]; //cnt[i]表示体积为i的背包的方案数

int main() {
    int N, V;  //物品数量，背包容量
    int v, w;  //物品体积，物品价值
    cin >> N >> V;
    
    for (int i = 0; i <= V; ++i) { //将dp数组全部初始化为负无穷大，dp[0]除外
        dp[i] = -inf;
    }
    dp[0] = 0;
    cnt[0] = 1; //数组cnt的初始化很简单，就是cnt[0] = 1;
    
    for (int i = 0; i < N; ++i) { //遍历物品
        cin >> v >> w;
        for (int j = V; j >= v; --j) { //遍历体积
            int tmp = max(dp[j], dp[j-v] + w); //先求出最大价值，再看其是从哪个状态转移得到的
            int sum = 0;
            if (tmp == dp[j]) sum += cnt[j]; //从状态dp[j]得到的，因此加上dp[j]的方案数cnt[j]
            if (tmp == dp[j-v]+w) sum += cnt[j-v]; //从状态dp[j-v]得到的，加上dp[j-v]的方案数cnt[j-v]
            if (sum >= mod) sum -= mod;
            dp[j] = tmp;
            cnt[j] = sum;
        }
    }
    
    int maxV = 0, res = 0; //由于容量为V的背包所能装的最大价值不一定会将物品装满，因此我们需要一一遍历每种容量，找到最大价值
    for (int i = 0; i <= V; ++i) maxV = max(maxV, dp[i]);
    for (int i = 0; i <= V; ++i) {
        if (dp[i] == maxV) res += cnt[i]; //找到一种方案数，累加即可
    }

    cout << res << endl;
    return 0;
}

9. 背包问题求具体方案

题目描述

题目链接

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

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

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

输出 字典序最小的方案。这里的字典序是指：所选物品的编号所构成的序列。物品的编号范围是 1…N。

输入格式

第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。

接下来有 N 行，每行两个整数 vi，wi，用空格隔开，分别表示第 i 件物品的体积和价值。

输出格式

输出一行，包含若干个用空格隔开的整数，表示最优解中所选物品的编号序列，且该编号序列的字典序最小。

物品编号范围是 1…N。

输入样例

4 5
1 2
2 4
3 4
4 6

输出样例

1 4

代码实现

我们定义dp[i][j]表示在背包容量为j的情况下，选择物品i及以后的物品所能得到的最大价值。这与我们之前的定义有些相反，但当前问题这样做更直观。这样做的话我们填充二维数组dp就得从i = n到i = 0来逆序填充了，因为这样才能用到之前记录的结果。

那么状态转移方程具体该怎么写呢？由于是01背包，每种物品只有选或者不选两种选择，我们已经知道物品需要逆序遍历，那么对于遍历到的每一个物品，分别决策选或不选两种选择。所以就有：

dp[i][j] = max(dp[i+1][j], dp[i+1][j-v]+w)

状态转移方程有了，如何得到具体选择方案呢？很简单，逆序反推就好了。我们从左到右遍历每种物品，判断其是否被选中，选中则输出，否则跳过。

那么如何判断每个物品是否被选中呢？根据二维数组dp。根据我们的定义，dp[1][V]一定是所能得到的最大价值，那么我们可以通过以下方法来判断物品1有没有被选中：

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

const int N_ = 1010;
int dp[N_][N_]; //dp[i][j]表示第i个到最后一个物品在背包容量为j的情况下能得到的最大价值
int v[N_], w[N_];

int main() {
    int N, V;
    cin >> N >> V;
    for (int i = 1; i <= N; ++i) {
        cin >> v[i] >> w[i];
    }
    for (int i = N; i >= 1; --i) { //由于此时dp[i][j]不同于之前的定义，因此需要反过来遍历
        for (int j = 0; j <= V; ++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]);
            }
        }
    }
    int left_v = V;
    for (int i = 1; i <= N; ++i) {
        //表示选择物品i
        if (left_v >= v[i] && dp[i][left_v] == dp[i+1][left_v-v[i]] + w[i]) {
            cout << i << " ";
            left_v -= v[i];
        }
    }
    
    return 0;
}

参考资料