☆❤背包问题

首先，我们要想象一下你正在去野餐的路上，你要决定要带什么东西。但是你有一个小背包，它只能装下一定的重量。

现在，你有一些物品可供选择，每个物品都有自己的重量和价值。你的目标是在不超过背包重量限制的情况下，选择一些物品，使它们的总价值最大化。

这就是背包问题的核心思想。

让我们以一个简单的例子来说明。假设你的背包最多只能承受5千克的重量。你有三个物品可供选择：一个苹果（重量2千克，价值3），一个书包（重量1千克，价值2），和一个水瓶（重量4千克，价值5）。

现在，你应该如何选择这些物品以使总价值最大化呢？

背包问题的一个常见解决方法是动态规划。我们可以创建一个表格来记录每个重量和物品的组合下，可以达到的最大总价值。

让我们创建一个表格，行表示物品，列表示重量。初始时，所有单元格都是0。

在这个例子中，我们可以按照以下步骤来填写表格：

1. 首先，我们考虑只有一个物品可供选择时的情况。对于第一个物品（苹果），我们从表格的第一行开始，如果重量小于等于5千克，我们将该单元格中的值设为苹果的价值3；否则，保持为0。

2. 接下来，我们考虑只有前两个物品可供选择时的情况。对于第二个物品（书包），我们从表格的第二行开始，如果重量小于等于5千克，我们将该单元格中的值设为书包的价值2；否则，保持为0。

3. 最后，我们考虑所有三个物品可供选择时的情况。对于第三个物品（水瓶），我们从表格的第三行开始，对于每个重量，我们可以选择将该物品放入背包或不放入背包。如果放入该物品，我们将其重量减去背包的重量限制，并在表格中查找剩余重量对应的单元格的值，然后将水瓶的价值加上该值，与不放入该物品时的价值进行比较，选择较大的值填入当前单元格。

填写完整个表格后，右下角的单元格将给出我们可以获得的最大总价值。

假设我们有三个物品可供选择：苹果、书包和水瓶，它们的重量和价值如下所示：

假设背包的重量限制是5千克。现在让我们创建一个3行（每个物品一行）x 6列（0到5千克的重量）的表格，并填写对应的数值。

填写表格的过程如下：

1、首先，我们考虑只有苹果这个物品可供选择时的情况。

  对于第一行（苹果），重量为2千克的苹果，我们检查背包的重量限制是否小于等于2千克。因为背包的重量限制是5千克，所以我们可以将苹果放入背包中，使得总价值为3；

2、接下来，我们考虑只有苹果和书包这两个物品可供选择时的情况。对于重量为1千克的书包，我们检查背包的重量限制是否小于等于1千克。因为背包的重量限制是5千克，所以我们可以将书包放入背包中，使得总价值为2。

；其他重量下的单元格保持为0。

3、最后，我们考虑所有三个物品可供选择时的情况。

对于重量为4千克的水瓶，我们可以选择将它放入背包中。此时剩余重量为5千克-4千克=1千克，查找表格中剩余重量为1千克时的总价值，为2。将水瓶的价值5与该值相加，得到总价值为7。

因此，在背包重量限制为5千克时，选择苹果和水瓶的组合可以使总价值最大化，总价值为7。

对于第三行（水瓶），我们需要考虑每个重量下的选择情况：

• 当重量为0千克时，无论是否选择水瓶，总价值都为0。

• 当重量为1千克时，无法放入水瓶，总价值与前一个重量（1千克）下的总价值相同，即为2。

• 当重量为2千克时，无法放入水瓶，总价值与前一个重量（2千克）下的总价值相同，即为3。

• 当重量为3千克时，无法放入水瓶，总价值与前一个重量（3千克）下的总价值相同，即为3。

• 当重量为4千克时，可以选择放入水瓶，此时剩余重量为4千克-4千克=0千克，查找表格中剩余重量为0千克时的总价值，为0。将水瓶的价值5与该值相加，得到总价值为5。

• 当重量为5千克时，可以选择放入水瓶，此时剩余重量为5千克-4千克=1千克，查找表格中剩余重量为1千克时的总价值，为2。将水瓶的价值5与该值相加，得到总价值为7。

填写表格后，得到如下所示的最终结果：

因此，在背包重量限制为5千克时，选择苹果和水瓶的组合可以使总价值最大化，总价值为7。

#include <iostream>
#include <vector>

using namespace std;

// 背包问题的动态规划解法
int knapsack(int W, vector<int>& weights, vector<int>& values) {
    int n = weights.size(); // 物品数量
    vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0)); // 创建二维数组dp，用于保存子问题的解

    // 递推计算子问题的解
    for (int i = 1; i <= n; ++i) { // 遍历每个物品
        for (int j = 1; j <= W; ++j) { // 遍历每个可能的背包容量
            if (weights[i - 1] <= j) {
                // 如果第i个物品的重量小于等于当前背包容量j
                // 有两种选择：放入第i个物品或不放入第i个物品
                dp[i][j] = max(dp[i - 1][j], values[i - 1] + dp[i - 1][j - weights[i - 1]]);
                // 在放入和不放入之间选择价值最大的方案
                // 如果放入第i个物品，将其价值加上剩余容量(j减去第i个物品重量)时的最大价值
            } else {
                // 如果第i个物品的重量大于当前背包容量j
                // 无法放入第i个物品，价值与前一个物品保持一致
                dp[i][j] = dp[i - 1][j];
            }
        }
    }

    return dp[n][W]; // 返回给定背包容量下的最大价值
}

int main() {
    int W = 10; // 背包容量
    vector<int> weights = {2, 3, 4, 5}; // 物品的重量
    vector<int> values = {3, 4, 5, 6}; // 物品的价值

    int max_value = knapsack(W, weights, values); // 计算可以获得的最大价值

    cout << "最大价值: " << max_value << endl; // 输出最大价值

    return 0;
}

下面是不用vector的代码：

#include <iostream>

using namespace std;

// 背包问题的动态规划解法
int knapsack(int W, int weights[], int values[], int n) {
    int dp[n + 1][W + 1]; // 创建二维数组dp，用于保存子问题的解

    // 初始化dp数组的第一行和第一列为0
    for (int i = 0; i <= n; ++i)
        dp[i][0] = 0;
    for (int j = 0; j <= W; ++j)
        dp[0][j] = 0;

    // 递推计算子问题的解
    for (int i = 1; i <= n; ++i) { // 遍历每个物品
        for (int j = 1; j <= W; ++j) { // 遍历每个可能的背包容量
            if (weights[i - 1] <= j) {
                // 如果第i个物品的重量小于等于当前背包容量j
                // 有两种选择：放入第i个物品或不放入第i个物品
                dp[i][j] = max(dp[i - 1][j], values[i - 1] + dp[i - 1][j - weights[i - 1]]);
                // 在放入和不放入之间选择价值最大的方案
                // 如果放入第i个物品，将其价值加上剩余容量(j减去第i个物品重量时)的最大价值
            } else {
                // 如果第i个物品的重量大于当前背包容量j
                // 无法放入第i个物品，价值与前一个物品保持一致
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    for (int i = 1; i <= n; ++i) { // 遍历每个物品
           for (int j = 1; j <= W; ++j) { // 遍历每个可能的背包容量
             cout<<dp[i][j]<<" ";
           }
           cout<<endl;
        }

    return dp[n][W]; // 返回给定背包容量下的最大价值
}

int main() {
    int W = 5; // 背包容量
    int weights[] = {2, 1, 4}; // 物品的重量
    int values[] = {3, 2, 5}; // 物品的价值
    int n = sizeof(weights) / sizeof(weights[0]); // 物品数量

    int max_value = knapsack(W, weights, values, n); // 计算可以获得的最大价值

    cout << "最大价值: " << max_value << endl; // 输出最大价值

    return 0;
}

在上述代码中，我们使用动态规划算法解决了背包问题。我们定义了一个二维数组 dp 来保存子问题的解，其中 dp[i][j] 表示在前 i 个物品中，背包容量为 j 时可以获得的最大价值。通过两层循环，我们按顺序计算所有子问题的解，并将最优解保存在 dp[n][W] 中，其中 n 是物品的数量，W 是背包的容量。

这个例子中，我们演示了如何使用动态规划算法解决背包问题，但实际上动态规划可以应用于各种具有重叠子问题和最优子结构性质的问题。根据问题的特点，我们需要确定问题的状态、定义状态转移方程，并按照初始化和递推计算的方式实现代码。

在上面的程序中，我们通过动态规划算法解决了背包问题。现在来详细说明一下状态的定义、状态转移方程和初始状态的含义。

1. 状态的定义： 在这个问题中，我们选择以背包中物品的数量和背包的容量作为状态。具体地，我们定义 dp[i][j] 表示在前 i 个物品中，背包容量为 j 时可以获得的最大价值。

2. 状态转移方程： 状态转移方程描述了如何根据已知状态计算出新状态的值。对于背包问题，我们可以根据以下方式来更新状态：

   
   

• 选择放入第 i 个物品，那么背包中的总价值为 values[i - 1] 加上前 i - 1 个物品在剩余容量 j - weights[i - 1] 时的最大价值，即 values[i - 1] + dp[i - 1][j - weights[i - 1]]。

• 不选择放入第 i 个物品，背包中的总价值为前 i - 1 个物品在容量 j 时的最大价值，即 dp[i - 1][j]。

• 如果第 i 个物品的重量 weights[i - 1] 小于等于当前背包容量 j，我们有两种选择：

• 我们需要在上述两种选择中选取较大的价值，将其赋值给 dp[i][j]，表示在前 i 个物品中，背包容量为 j 时可以获得的最大价值。

因此，状态转移方程可以表示为：
dp[i][j] = max(dp[i - 1][j], values[i - 1] + dp[i - 1][j - weights[i - 1]])

1. 初始状态： 初始状态指的是边界情况或者基础情况下的状态值。对于背包问题，初始状态是背包容量为 0 时的最大价值，即 dp[i][0] = 0。另外，当没有物品可选时，即 i = 0 时，背包中的总价值也是 0，即 dp[0][j] = 0。

通过上述的状态定义、状态转移方程和初始状态，我们可以使用动态规划算法解决背包问题，计算出在给定背包容量下能够获取的最大价值。