背包问题

2023-04-03 3102 words 7 minutes

Contents

背包问题是一类经典的动态规划问题，它非常灵活、变体多样，需要仔细体会。本书只介绍两类最简单的背包问题:01 背包问题和完全背包问题，而这两种背包中，又以01 背包为重。 01背包问题 有n件物品，每件物品的重量为 w[i]，价值为c[i]。现有一个容量为V的背包，问如何选取物品放入背包，使得背包内物品的总价值最大。其中每种物品都只有1件。

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

令dp[i][v]表示前i件物品(1<i<n, 0<v<V)装入容量为v的背包中所能获得的最大价值。考虑对第i件物品的选择策略，有两种策略： (1) 不放第件物品那么问题转化为前i-1件物品装入容量为v的背包中所能获得的最大价值，也即dp[i-1][v]。 (2) 放第i件物品，那么问题转化为前i-1件物品装入容量为v-w[i]的背包中所能获得的最大价值，也即dp[i-1][v-w[i]]+c[i]。

// @FileName:     bagpack1.cpp
// @CreateTime:   2023/04/05 10:17:33
// @Author:       Rainbow River

#include <iostream>
using namespace std;
/*
0-1背包问题: 先看如何设置状态, 需要考察状态的维度, 例如本题中有两个维度
分别是 物品质量和背包容量, 具体的dp[i][v]是指仅考虑前i个物品且背包质量
为 v 的情况下获得的最大价值
*/

const int MAXN = 101;
int w[MAXN], c[MAXN];   // w[] 物品质量数组, v[] 物品价值数组
int n, bag;     // n 物品数量, bag 背包容量
int dp[MAXN][MAXN];     // dp[i][v] 状态数组
int p[MAXN][MAXN];     // 回溯数组

void init_problem(){
    cin >> n >> bag;
    for(int i=1; i<=n; i++)
        cin >> w[i];
    for(int i=1; i<=n; i++)
        cin >> c[i];
}

void solve_probem(){
    // dp[0][]=0, dp[][0]=0
    for(int i=1; i<=n; i++){
        for(int v=1; v<=bag; v++){
            if(v >= w[i] && (dp[i-1][v-w[i]]+c[i]) > dp[i-1][v]){
                dp[i][v] = dp[i-1][v-w[i]]+c[i];
                p[i][v] = 1;   // 表示选择第 i 件物品
            }else{ // v容量太小, 无法装入 w[i] 或者 装入物品i后得不到更大的价值
                dp[i][v] = dp[i-1][v];    
                p[i][v] = -1;  // 表示不选第 i 件物品
            }
        }
    }
}

void path_tracing(int i, int v){
    // 从[n, bag] 开始回溯
    if(i<=0 || bag<=0){
        cout << "Get it: " << endl;
    }else{
        if(p[i][v] == -1)
            path_tracing(i-1, v);
        if(p[i][v] == 1){
            path_tracing(i-1, v-w[i]);
            cout << "Put object " << i << ", ("<< w[i] << ", " << c[i] << ")" << endl;
        }
    }
}

int main(){
    init_problem();
    solve_probem();
    path_tracing(n, bag);
    cout << dp[n][bag] << endl;
    return 0;
}
/*
5 8
3 5 1 2 2
4 5 2 1 3

*/

可以知道，时间复杂度和空间复杂度都是 O(nV)，其中时间复杂度已经无法再优化，但是空间复杂度还可以再优化. 注意到状态转移方程中计算dp[i][v]时总是只需要dp[i-1][v]左侧部分的数据(即只需要图中正上方与左上方的数据)，且当计算dp[i+1]的部分时，dp[i-1]的数据又完全用不到了，因此不妨仅设立一维数组 dp[v]。每计算出一个dp[i][v]，就相当于把 dp[i-1][v]抹消，因为在后面的运算中dp[i-1][]再也用不到了。我们把这种技巧称为滚动数组。

// @FileName:     bagpack2.cpp
// @CreateTime:   2023/04/05 15:13:44
// @Author:       Rainbow River
#include <iostream>
using namespace std;
const int MAXN = 101;
int w[MAXN], c[MAXN];   // w[] 物品质量数组, c[] 物品价值数组
int n, bag;     // n 物品数量, bag 背包容量
// 滚动数组: dp[v] = max(dp[v], dp[v-w[i]]+c[i])
int dp[MAXN];     // dp[v] 状态数组

void info(int a[]){
    for(int i=1; i<=bag; i++)
        cout << a[i] << " ";
    cout << endl;
}

void init_problem(){
    cin >> n >> bag;
    for(int i=1; i<=n; i++)
        cin >> w[i];
    for(int i=1; i<=n; i++)
        cin >> c[i];
}

void solve_probem(){
    for(int i=1; i<=n; i++){
        for(int v=bag; v>=w[i]; v--)    // 逆序, 保证dp[v-w[i]]是未被更新过的(i-1的状态)
            dp[v] = max(dp[v-w[i]]+c[i], dp[v]);
    }
}

int main(){
    init_problem();
    solve_probem();
    cout << dp[bag] << endl;
    return 0;
}

动态规划是如何避免重复计算的问题在01背包问题中非常明显。在一开始暴力枚举每件物品放或者不放入背包时，其实忽略了一个特性:第件物品放或者不放而产生的最大值是完全可以由前面i-1件物品的最大值来决定的，而暴力做法无视了这一点。另外，01 背包中的每个物品都可以看作一个阶段，这个阶段中的状态有dp[i][0] ~ dp[i][V]，它们均由上一个阶段的状态得到。事实上，对能够划分阶段的问题来说，都可以尝试把阶段作为状态的一维，这可以使我们更方便地得到满足无后效性的状态。从中也可以得到这么一个技巧，如果当前设计的状态不满足无后效性，那么不妨把状态进行升维，即增加一维或若干维来表示相应的信息，这样可能就能满足无后效性了.

完全背包问题

完全背包问题的叙述如下: 有n种物品，每种物品的单件重量为 w[i]，价值为c[i]。现有一个容量为V的背包，问如何选取物品放入背包，使得背包内物品的总价值最大。其中每种物品都有无穷件。可以看出，完全背包问题和01 背包问题的唯一区别就在于:完全背包的物品数量每种有无穷件，选取物品时对同一种物品可以选1件选2件……只要不超过容量 V 即可，而01背包的物品数量每种只有1件。

状态数组和01背包完全相同，但由于第i件物品可以是多个，所以是转到[i][v-w[i]]: dp[v] = max(dp[i-1][v], dp[i][v-w[i]]+c[i]) 可以看到, dp[i][v-w[i]]+c[i]部分中 dp[i] 是已被更新后的 i 状态, 因此转为1维后应正向遍历.

总结

前面几节介绍了动态规划的相关概念，并求解了一些经典的动态规划模型。但是在实际碰到新的问题时，初学者总是容易陷入头脑一片空白、完全无法设计状态的情况，这是正常现象，因为动态规划本身就需要经验的积累和大量做题才能有较大的提高。不过从上面的经典模型中还是能总结出一些规律性的东西，先把前面介绍过的动态规划模型列举如下: (1)最大连续子序列和令dp[i]表示以A[i]作为末尾的连续序列的最大和 (2)最长不下降子序列(LIS) 令dp[i]表示以A[i]结尾的最长不下降子序列长度。 (3)最长公共子序列(LCS) 令dp[i][j]表示字符串A的i号位和字符串B的i号位之前的LCS长度 (4)最长文子串令dp[i][j]表示 S[i]至 S[j]所表示的子串是否是回文子串。 (5)数塔DP 令dp[i][j]表示从第i行第j个数字出发的到达最底层的所有路径上所能得到的最大和。 (6)DAG最长路令dp[i]表示从i号顶点出发能获得的最长路径长度 (7)01背包令dp[i][v]表示前i件物品装入容量为v的背包中能获得的最大价值。 (8)完全背包令dp[i][v]表示前i件物品放入容量为v的背包中能获得的最大价值。

先看(1)~(4)，这4个都是关于序列或字符串的问题(特别说明:一般来说，“子序列”可以不连续，“子串”必须连续)。可以注意到，(1)(2) 设计状态的方法都是“令 dp[i]表示以A[i]为结尾的XXX”，其中XX即为原问题的描述，然后分析A[i]的情况来进行状态转移;而(3)(4)由于原问题本身就有二维性质，因此使用了“令 dp[i][j]表示i号位和j号位之间XXX”的状态设计方式，其中XXX为原问题的描述(最长回文子串中的状态和原问题有关;当然，最长回文子串的状态也可以设计成“令 dplil]表示 Si]至 Si]的区间的最长回文子串长度”，并且可解)。这就给了我们一些启发: 当题目与序列或字符串(记为 A)有关时，可以考虑把状态设计成下面两种形式，然后根据端点特点去考虑状态转移方程。 (1) 令dp[i][j]表示以A[i]结尾(或开头)的XXX (2) 令dp[i][j]表示A[i]至A[j]区间的XXX。其中XXX均为原问题的表述。接着来看(5)~(8)，可以发现它们的状态设计都包含了某种“方向”的意思。如数塔DP 中设计为从点(i, j)出发到达最底层的最大和，DAG 最长路中设计为从i号顶点出发的最长路，背包问题中则设计成dp[i][v]表示前i件物品恰好放入容量为的背包中能获得的最大价值。这又说明了一类动态规划问题的状态设计方法:分析题目中的状态需要几维来表示，然后对其中的每一维采取下面的某一个表述:

恰好为i。
前i. 在每一维的含义设置完毕之后，dp 数组的含义就可以设置成“令 dp 数组表示恰好为i(或前i), 恰好为j(或前j)……的XXX”其中XX为原问题的描述。接下来就可以通过端点的特点去考虑状态转移方程。最后需要说明的是，在大多数的情况下，都可以把动态规划可解的问题看作一个有向无环图(DAG)，图中的结点就是状态，边就是状态转移的方向，求解问题的顺序就是按照DAG的拓扑序进行求解。从这个角度可以辅助理解动态规划，建议读者能结合讲解过的几个动态规划模型予以理解