01背包模型

• 一般适用为：在有限的体积下，每个物品最多只能使用一次的情况下，求所选物品的最大价值

• 分析方法为：可以将求解的问题考虑成一个集合，根据选或者不选第i个物品将集合分成两类：

  1. 选第·i个物品
  2. 不选第i个物品

  然后求这两个区间中价值的最大值，即为最终答案

举例应用：

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

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

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

输入格式：

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

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

输出格式：

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

数据范围：

0 < N, V <= 1000，0 < vi, wi <= 1000

状态表示：

题目中限制最多使用N件物品，并且物品总体积不超过V,可以定义二维数组f[i][j]

• f[i][j]表示所有只考虑前i件物品，且总体积不超过j的选法的集合

由于本题中要求的是最大价值，所以：

• f[i][j]中的元素就表示在只考虑前i件物品，且总体积不超过j的所有选法中的物品价值总和最大的值

状态计算：

定义好状态之后，开始计算每个状态的值：

• 初始化f数组

由于i表示只考虑前i件物品，也就是只从前i件物品中选择，而当i为0时，只从前0件物品中选，也就是不选择物品，那么无论背包的体积有多大，总价值都为0，所以有：

f[0][j] = 0 (0 <= j <= V)

这样就完成了f数组的初始化，由于定义f数组时会默认将数组中的值都赋值为0，所以实际上不需要写初始化的语句

• 遍f数组，根据初始值来不断更新f数组中的其他值

  • 如何根据初始值来更新其他值：

    • 在01背包的分析方法中，是根据选或者不选第i个物品来将一个集合来划分成选第i个物品和不选第i个物品两个集合的

    • 由于f数组表示的是所有只考虑前i件物品，且总体积不超过j的选法的集合，表示的是一个集合，且重点在于从前i个物品中选择。那么根据划分依据，可以将f[i][j]表示的集合划分为：

      1. 所有只考虑前i - 1件物品，且总体积不超过j的选法，一定选第i件物品（要注意如果当前的体积j小于第i件物品的体积，那么就选不了第i件物品，那么此子集不存在，也就不用考虑了

         由于一定选第i件物品，所以这个集合的总价值可以表示为：f[i - 1][j - vi] + wi

      2. 所有只考虑前i - 1件物品，且总体积不超过j的选法，一定不选第i件物品

         由于不选第i件物品，所以这个集合的总价值可以表示为：f[i - 1][j]

    • 由于这两个划分后的子集合的并集恰好为划分之前的大集合，所以有：

      f[i][j] = max(f[i - 1][j], f[i - 1][j - vi] + wi)

      因此根据此递推式就可以更新f数组中的其他值

• 根据f数组中初始化的值和分析得到的递推式，可以通过循环得到f数组中每个元素的值：

    // 由于f[0][j]初始化为0，所以不用写f数组的初始化语句

    // 循环递推：
    // n为物品的件数，m为背包的体积
    for (int i = 1; i <= n; i ++ )
        for (int j = 0; j <= m; j ++ )
        {
            f[i][j] = f[i - 1][j]; // 第二种情况一定存在
            if (j >= vi) // 在此条件下第一种情况才存在
                f[i][j] = max(f[i][j], f[i - 1][j - vi] + wi);
        }

这样我们就算出了f数组中每个元素的值

• 题目中给出了n件物品，且背包总体积为m，那么题目中要求就是：只考虑前n件物品，且总体积不超过m的所有选法中总价值最大的价值数，

• 恰好对应于f[n][m]，且f[n][m]所表示的元素就是此集合下的最大价值，那么答案即为f[n][m]

总结：

最后再总结一下过程并给出总代码：

01背包dp
    状态表示：
        集合：所有只考虑前i - 1件物品，且总体积不超过j的选法的集合
        属性：此集合下的最大价值
    状态计算：
        // 划分依据：选或者不选第i件物品
        初始化：f[0][j] = 0; (0 <= j <= m)
        计算：
            f[i][j] = max(f[i][j], f[i - 1][j - vi] + wi);

总代码：

#include <iostream>

using namespace std;

const int N = 1010, M = N; // 多开10个空间防止溢出

int n, m;
int v[N], w[N];
int f[N][M];

int main()
{
    scanf("%d%d", &n, &m); // 用cin输入也可以，一般情况下scanf的输入速度优于cin
    for (int i = 1; i <= n; i ++ ) scanf("%d%d", &v[i], &w[i]);

    // 循环遍历f数组
    for (int i = 1; i <= n; i ++ )
        for (int j = 0; j <= m; j ++ )
        {
            f[i][j] = f[i - 1][j]; // 第二种情况一定存在
            if (j >= v[i]) // 在此条件下第一种情况才存在
                f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
        }

    printf("%d\n", f[n][m]);

    return 0;
}

01背包的优化：

• 一般情况下，背包问题的优化都是在空间复杂度上的优化

• 而且在空间上的优化主要是对代码做等价替换

• 对v[i]和w[i]两个数组空间的优化：

分析代码：

for (int i = 1; i <= n; i ++ )
    for (int j = 0; j <= m; j ++ )
    {
        f[i][j] = f[i - 1][j]; // 第二种情况一定存在
        if (j >= v[i]) // 在此条件下第一种情况才存在
            f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
}
  ```

  我们可以发现，在外层循环第`i`层循环中，我们只用到了`v[i]`和`w[i]`，因此我们可以在循环时一边输入`v[i]`和`w[i]`，一边根据`v[i]`和`w[i]`的值进行计算，这样我们就只用`v`和`w`两个变量代替了两个数组，减少了空间使用量，主要代码如下：

for (int i = 1; i <= n; i )
{
int v, w;
scanf(“%d%d”, &v, &w);
for (int j = 0; j <= m; j )
{
f[i][j] = f[i - 1][j]; // 第二种情况一定存在
if (j >= v) // 在此条件下第一种情况才存在
f[i][j] = max(f[i][j], f[i - 1][j - v] + w);
}
}
```

1. 对f[i][j]数组空间的优化：

   • 首先举一个例子便于理解：

     假设有一个数组为：int a[5] = {1, 2, 3, 4, 5};

     现有根据下列条件更新a数组中的值：

     a数组中的元素满足：

     • a[0] = 0;
     • a[i] = max(a[i], a[i - 1]); (i >= 1)

     如何更新a数组中的值？

     我们可以创建一个数组int b[5]，让b数组存储更新后的a数组中的值，那么有：

     • b[0] = 0;
     • b[i] = max(a[i], a[i - 1]); (i >= 1)

     我们就可以得到更新后的a数组中的值。

     但这种方法开辟了一个新的数组空间，空间复杂度高

     • 如何减少空间的使用？

     我们可以发现a[i]的更新只用到了小于等于i的a[i]的值

     如果从小到大更新a数组，那么更新a[1] = max(a[0], a[1])之后，再更新a[2] = max(a[2], a[1])时，由于a[1]的值已经被更新，不再是之前的值，所以这种方法是失败的。

     如果从大到小更新a数组呢？

     ​ 那么我们可以用直接用a[4]和a[3]的值更新a[4]

     ​ 更新a[4]之后，我们更新a[3]时只用到了a[3]和a[2]的值，并没有用更新后的a[4]的值，

     ​ 依次下去……

     ​ 可以发现用这种从大到小更新a数组的方法可以成功地更新整个a数组

     ​ 那么我们就成功地在不开辟新空间的情况下更新了整个a数组

     ​ 也附上代码：

     ```cpp
     int a[5] = {1, 2, 3, 4, 5};

     for (int i = 4; i >= 1; i – )
     a[i] = max(a[i], a[i - 1]);
     a[0] = 0; // 最后更新a[0]
     ```

   理解上述问题之后，我们再来看01背包中f[i][j]数组的优化

   分析代码：

   cpp for (int i = 1; i <= n; i ++ ) for (int j = 0; j <= m; j ++ ) { f[i][j] = f[i - 1][j]; // 第二种情况一定存在 if (j >= v[i]) // 在此条件下第一种情况才存在 f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]); }

   对于f[i][j]数组的计算，我们只用到了f[i - 1][j]和f[i - 1][j - v[i]]

   可以发现在计算第i层的第j个元素（也就是f[i][j]时），我们只用到了第i - 1层的第j或者j - v[i]个元素，也就是小于等于j的f[i - 1][j]的值。

   • 本质上就是用小于等于j的f[i - 1][j]的值（类比于之前的b数组）来更新f[i][j]（类比于之前的a数组），只不过f[j - v[i]]多加了一项w[i]，更新时加上即可

   将内层循环比作遍历求a数组的过程，将外层循环比作不断更新a数组的过程，此时我们就可以用同样的方法来优化空间:

   • 首先将int f[N][M]重新定义为int f[M]

     此时更新f数组的内层循环变为：for (int j = m; j >= 0; j -- )

   • 由于当j < v[i]时，f[i][j] = f[i - 1][j],类比于a[i] = a[i]，所以此情况下优化之后为f[j] = f[j]，无需更新f[j]数组

   • 只有当j >= v[i]时，优化之后才有f[j] = f[j] + (f[j - v[i]] + w[i])，此情况下需要更新f[j]数组，所以从大到小循环时只需要从m循环到v[i]即可

     所以最终内层循环为：for (int j = m; j >= v[i]; j -- )

   所以循环可以优化为：

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

将两个优化方面结合一下，可以得到最终的优化代码：

for (int i = 1; i <= n; i ++ )
{
    int v, w;
    scanf("%d%d", &v, &w);
    for (int j = m; j >= v; j -- )
        f[j] = max(f[j], f[j - v] + w);
}

由于经过了n次更新，所以最终的f[m]相当于f[n][m]

至此，01背包的优化就已经结束。

最后附上优化后的完整代码：

#include <iostream>

using namespace std;

const int M = 1010; // 多开10个空间防止溢出

int n, m;
int f[M];

int main()
{
    scanf("%d%d", &n, &m);

    // 循环遍历f数组
    for (int i = 1; i <= n; i ++ )
    {
        int v, w;
        scanf("%d%d", &v, &w);
        for (int j = m; j >= v; j -- )
            f[j] = max(f[j], f[j - v] + w);
    }

    printf("%d\n", f[m]);

    return 0;
}