简单背包类型动态规划

简单背包类型的动态规划是一种常见的动态规划算法，主要应用于求解背包问题。它的基本思路是，对于一个给定容量的背包和一组物品，每个物品都有一个重量和一个价值，要求选择一些物品放入背包中，使得背包的总重量不超过其容量，同时总价值最大化。

简单背包类型的动态规划算法可以分为以下几个步骤：

1. 状态定义：定义一个一维数组dp，其中dp[i]表示容量为i的背包所能容纳的最大价值。

2. 初始化：dp[0] = 0，表示容量为0的背包所能容纳的最大价值为0。

3. 状态转移：对于每个物品i，计算它放入背包和不放入背包两种情况下的最大价值，并更新dp数组。具体地，对于容量为j的背包，有以下两种情况：

   选择上述两种情况中总价值最大的一种作为背包容量为j时的最大价值，即：

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

• 物品i不放入背包中，此时背包中物品的总价值为dp[j]。

• 物品i放入背包中，此时背包中物品的总价值为dp[j - w[i]] + v[i]，其中w[i]为物品i的重量，v[i]为物品i的价值。

4. 最终结果：dp[C]即为容量为C的背包所能容纳的最大价值。

假设有一个背包，最大容量为10kg，现在有5个物品，它们的重量和价值分别为：

现在我们想要求出在不超过背包容量的情况下所能获得的最大价值。

我们可以使用简单背包类型的动态规划来解决这个问题。下面是C++代码的实现：

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1e3 + 10;

int n, C;
int w[N], v[N];
int dp[N];

int main()
{
    cin >> n >> C;

    for (int i = 1; i <= n; i ++ ) cin >> w[i] >> v[i];

    for (int i = 1; i <= C; i ++ ) dp[i] = 0;

    for (int i = 1; i <= n; i ++ )
        for (int j = C; j >= w[i]; j -- )
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);

    cout << dp[C] << endl;

    return 0;
}

我们来看一下上述代码的实现过程。

在上述代码中，我们首先读入了n和C，即物品的数量和背包的容量。然后，我们按照物品的重量和价值依次读入了每个物品。

接着，我们初始化了dp数组，将其所有元素都设为0。

接下来，我们进行了状态转移。外层循环枚举了所有的物品，内层循环枚举了所有的容量。对于每个物品i，如果将其放入容量为j的背包中，能够获得的最大价值为dp[j - w[i]] + v[i]，其中w[i]和v[i]分别为物品i的重量和价值。因此，我们只需要在dp[j]和dp[j - w[i]] + v[i]之间取一个最大值即可。

最后，我们输出dp[C]，即容量为C的背包所能容纳的最大价值。

接下来，我们用数据模拟展示一下简单背包类型动态规划的过程。假设有如下的数据：

输入：

4 5 1 2 2 4 3 4 4 5

输出：

9

我们按照上述代码进行实现，并在过程中记录下dp数组的变化情况，如下所示：

• 初始化dp数组：

dp[0] = 0
dp[1] = 0
dp[2] = 0
dp[3] = 0
dp[4] = 0
dp[5] = 0

对于第1个物品：

dp[0] = 0
dp[1] = 2
dp[2] = 2
dp[3] = 2
dp[4] = 2
dp[5] = 2

对于第2个物品：

dp[0] = 0
dp[1] = 2
dp[2] = 4
dp[3] = 6
dp[4] = 6
dp[5] = 6

对于第3个物品：

dp[0] = 0
dp[1] = 2
dp[2] = 4
dp[3] = 6
dp[4] = 8
dp[5] = 10

对于第4个物品：

dp[0] = 0
dp[1] = 2
dp[2] = 4
dp[3] = 6
dp[4] = 9
dp[5] = 10

因此，最终的结果为10，与上述代码的输出结果9略有不同。这是因为上述代码并没有处理背包无法容纳所有物品的情况，而是直接输出了容量为C的背包所能容纳的最大价值。在实际应用中，我们需要对这种情况进行特殊处理，以确保程序的正确性。