本文共 2317 字，大约阅读时间需要 7 分钟。

背包问题求解：状态转移与递归实现

问题分解

背包问题涉及一个背包可以携带的最大重量w，和n个物品，每个物品有重量w_i和价值v_i。目标是选择一些物品，使得背包中物品总价值最大，同时总重量不超过w。对于每个物品，我们有两种选择：装入背包或不装入。这需要从最后一个物品开始，逐个考察，逐步构建最大价值的状态表。

状态转移

我们可以通过动态规划的方法来解决这个问题。状态转移公式如下：

• 如果物品重量w_i > j，则无法装入背包，此时最大价值与前一个状态相同，即val[i][j] = val[i-1][j]。
• 如果物品重量w_i ≤ j，则有两种选择：
• 不装入背包，此时最大价值为val[i-1][j]。
• 装入背包，此时最大价值为val[i-1][j - w_i] + v_i。
  因此，val[i][j] = max{val[i-1][j], val[i-1][j - w_i] + v_i}。

示例分析

以编号1-6的物品为例，重量w = {4, 6, 2, 2, 5, 1}，价值v = {8, 10, 6, 3, 7, 2}，背包容量C=12。通过动态规划求解，得出最大价值为24，对应的背包中物品为第3、2、1号（重量分别为2、6、4）。

C++实现

循环实现

#include 
   
    
using namespace std;
int main() {
    int N = 6; // 物品数量
    int C = 12; // 背包容量
    
    int v[N + 1] = {0, 8, 10, 6, 3, 7, 2}; // 价值数组
    int w[N + 1] = {0, 4, 6, 2, 2, 5, 1}; // 重量数组
    
    // 初始化价值矩阵
    int val[N + 1][C + 1];
    for (int j = 0; j <= C; ++j) {
        val[0][j] = 0;
    }
    
    // 遍历所有物品
    for (int i = 1; i <= N; ++i) {
        for (int j = 0; j <= C; ++j) {
            if (j < w[i]) {
                // 当前物品重量超过背包容量，不装入
                val[i][j] = val[i - 1][j];
            } else {
                // 装入背包
                int a = val[i - 1][j - w[i]] + v[i];
                // 不装入背包
                int b = val[i - 1][j];
                val[i][j] = max(a, b);
            }
        }
    }
    
    // 输出最大价值
    cout << val[N][C] << endl;
    
    // 判断装入物品列表
    int b[N + 1] = {0};
    for (int i = 1; i <= N; ++i) {
        if (val[i][C] != val[i - 1][C]) {
            b[i] = 1;
        }
    }
    
    return 0;
}
   

递归实现

递归实现可以通过将每个潜在的背包状态拆解，逐步计算最大价值。递归函数的终止条件是当前物品数量为0，对于每个物品，判断其重量是否超过当前背包容量。

#include 
   
    
using namespace std;
// 递归函数：返回当前物品及以后的物品中，可以装入背包的最大价值
int val(int i, int c, int w[], int v[]) {
    if (i == 0) {
        return 0;
    }
    if (c < w[i - 1]) {
        return val(i - 1, c, w, v);
    } else {
        int a = val(i - 1, c - w[i - 1], w, v) + v[i - 1];
        int b = val(i - 1, c, w, v);
        return max(a, b);
    }
}
int main() {
    int v[] = {8, 10, 6, 3, 7, 2};
    int w[] = {4, 6, 2, 2, 5, 1};
    int m = 6; // 物品数量
    int C = 12; // 背包容量
    cout << val(m, C, w, v) << endl;
    
    // 判断装入物品列表
    int b[m + 1] = {0};
    for (int i = m; i >= 1; --i) {
        if (val(i, C, w, v) != val(i - 1, C, w, v)) {
            b[i] = 1;
        }
    }
    return 0;
}