0-1背包问题思路分析，重点解释一维dp数组的01背包问题为什么要倒序遍历背包，以及为什么不能先遍历背包，只能先遍历物品_背包问题先遍历物品还是背包

---

前言

对0-1背包问题的二维dp数组以及一维dp数组的思路分析
来源：代码随想录 link

本文是我对01背包问题的理解，在本文中具体分析dp数组的形成过程，最核心的地方就是我对每种情况下的01背包问题给出了代码运行结果，便于读者理解。
重点解释了为什么一维dp数组的01背包问题为什么要倒叙遍历背包，以及为什么不能先遍历背包，只能先遍历物品。

1，一维dp数组为什么不能正序遍历书包？
因为正序遍历背包会导致同一个物品被放了两次，但是01背包要求同一物品只能被放一次。

2，一维dp数组为什么不能先遍历背包？
因为能用一维dp数组解决01背包问题的原理就是先遍历物品时dp数组是一行一行形成的（具体过程正文中有结果显示），下一行的数据只受到上一行数据的影响，因此可以只用一维数组去解决01背包问题，但是先遍历书包时dp数组时一列一列形成的（具体过程正文中有结果显示），这二者本质上就是相悖的，如果要强行理解的话，就是如果先遍历背包时，只会往背包中放入一件物品（正文中有具体结果演示）。

---

一、0-1背包问题

有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大

举例说明：假设背包最大重量为4，物品的重量以及价值如表所示：

下面分别通过二维db数组以及一维dp数组进行分析。

二、二维dp数组01背包问题代码详解

1.递推关系式

dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
1

dp[i][j]：从物品0到物品i中任意取，放入容量为j的背包，可放入物品的最大价值为dp[i][j]。
递推关系式的含义为：01背包问题可以分解为不放物品i和放物品i
即dp[i][j]为放物品i和不放物品i的得到的价值的最大值。

2.代码详解

2.1先遍历物品

根据代码随想录的介绍，二维dp数组的01背包问题先遍历物品还是先遍历背包均可。
如果先遍历物品，代码如下：
其中为了看到每次遍历后dp数组的变化，我将其打印输出，以便分析。

#include<iostream>
#include<vector>
#include <iomanip>
using namespace std;
//打印dp数组
void print_dparr(vector<vector<int>>& dp)
{
    int row = dp.size();
    int col = dp[0].size();
    for (int i = 0;i < row;i++)
    {
        for (int j = 0;j < col;j++)
        {
            cout <<std::left << setw(2) << dp[i][j] << " ";
        }
        cout << endl;
    }
    cout << endl;
}

void test_2_wei_bag_problem1() {
    vector<int> weight = { 1, 3, 4 };
    vector<int> value = { 15, 20, 30 };
    int bagweight = 4;

    // 二维数组
    vector<vector<int>> dp(weight.size(), vector<int>(bagweight + 1, 0));

    // 初始化
    for (int j = weight[0]; j <= bagweight; j++) {
        dp[0][j] = value[0];
      
    }
    cout << "从物品0中取物品" << endl;
    print_dparr(dp);
    // weight数组的大小 就是物品个数
    for (int i = 1; i < weight.size(); i++) { // 遍历物品
        for (int j = 0; j <= bagweight; j++) { // 遍历背包容量
            if (j < weight[i]) dp[i][j] = dp[i - 1][j];
            else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
        }
        cout << "从物品0"<<"到物品"<<i << "中取物品" << endl;
        print_dparr(dp);
    }
    cout <<"最终结果为:"<< dp[weight.size() - 1][bagweight] << endl;
}
int main() {
    test_2_wei_bag_problem1();
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

代码运行结果如下：

dp数组形成过程

先遍历物品时，整个dp矩阵的下一行数据由上一行数据计算得到，这也为使用一维dp数组解决01背包问题埋下伏笔。

2.2.先遍历背包

同理先遍历背包再遍历物品可以得到相同结果，但是此时由于遍历顺序的改变，dp数组的形成过程发生了变化，首先附上代码：

#include<iostream>
#include<vector>
#include <iomanip>
using namespace std;
//打印dp数组
void print_dparr(vector<vector<int>>& dp)
{
    int row = dp.size();
    int col = dp[0].size();
  
    for (int i = 0;i < row;i++)
    {
        for (int j = 0;j < col;j++)
        {
            cout <<std::left << setw(2) << dp[i][j] << " ";
        }
        cout << endl;
    }
    cout << endl;
}

void test_2_wei_bag_problem1() {
    vector<int> weight = { 1, 3, 4 };
    vector<int> value = { 15, 20, 30 };
    int bagweight = 4;
    // 二维数组
    vector<vector<int>> dp(weight.size(), vector<int>(bagweight + 1, 0));
    // 初始化
    for (int j = weight[0]; j <= bagweight; j++) {
        dp[0][j] = value[0];  
    }
    // weight数组的大小 就是物品个数
    // 遍历物品
    int i;
    for (int j = 0; j <= bagweight; j++) { // 遍历背包容量
        for ( i = 1; i < weight.size(); i++) {
            if (j < weight[i]) dp[i][j] = dp[i - 1][j];
            else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
        }
        cout << "从物品0到物品2中取物品放到容量为"<<j<<"的背包" << endl;
        print_dparr(dp);
    }

    cout <<"最终结果为:"<< dp[weight.size() - 1][bagweight] << endl;
}

int main() {
    test_2_wei_bag_problem1();
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

代码运行结果如下：

dp数组形成过程

dp数组形成过程分析

由不同的遍历顺序的运行结果可知，先便利物品时dp数组是一行一行形成的，而先遍历背包时，dp数组是一列一列形成的。
如果先遍历物品，则其思想为从物品0到物品i中选物品放入容量为4的背包中得到的最大价值，其中i由0取到2。
如果先遍历背包，则其思想为从物品0到物品2中选物品放到容量为j的背包中得到的最大价值，其中j由0取到4。

根据递推关系式可知 dp[i][j] 与 i-1 行的 0 到 j-1 这些数据有关，这个思想对理解一维dp数组为什么倒序遍历很有用。
二维dp数组的01背包问题较好理解，下面介绍一维dp数组的01背包问题。

三、一维dp数组01背包问题代码详解

1.递推关系式

利用滚动数组的形式将二维数组降为一维数组，目前考虑先遍历物品的情况，后续分析先遍历背包的情况。

dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
1

可以写成一维形式的原因在上述二维dp数组中其实已经略微阐述了一下，现在进行详细分析。
在上述分析中，我们知道dp[i][j] 只与 i-1 行的 0 到 j-1 这些数据有关，即dp矩阵的下一行数据只与上一行的一些数据有关，因此完全可以利用一维数组重复使用。
此时dp[j]的含义为：容量为j的背包可以背的最大价值。

2.代码详解

背包倒序遍历

下面分析一下先遍历物品时的一维dp数组解决01背包问题的代码，注意此时是倒序遍历背包：

#include<iostream>
#include<vector>
#include <iomanip>
using namespace std;
void print_dparr(vector<int>& dp)
{
    int col = dp.size();
        for (int j = 0;j < col;j++)
        {
            cout << std::left << setw(2) << dp[j] << " ";
        }
    cout << endl;
    cout << endl;
}
void test_1_wei_bag_problem() {
    vector<int> weight = { 1, 3, 4 };
    vector<int> value = { 15, 20, 30 };
    int bagWeight = 4;

    // 初始化
    vector<int> dp(bagWeight + 1, 0);
    for (int i = 0; i < weight.size(); i++) { // 遍历物品
        for (int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
            dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
        }
        cout << "从物品0到物品" << i << "取物品放到背包中" << endl;
        print_dparr(dp);
    }
    cout <<"最终结果为："<< dp[bagWeight] << endl;
}
int main() {
    test_1_wei_bag_problem();
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

运行结果为：

可以看到dp数组的形成过程与二维dp数组的形成过程一致，只不过此时的dp数组是一维的，把三个一维dp数组拼在一起便形成了二维dp数组的形式。

背包正序遍历

在一维dp数组求解01背包问题中很重要的一点就是书包的遍历顺序，此时书包的遍历顺序只能是倒序遍历，具体原因如下：

首先先将代码改成正序遍历的形式，具体代码在此不再赘述，只需要把上述代码的循环改成如下形式：

  for (int i = 0; i < weight.size(); i++) { // 遍历物品
        for (int j = 0; j <= bagWeight; j++) {// 遍历背包容量
            if (j < weight[i]) continue;
            dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
        }
        cout << "从物品0到物品" << i << "取物品放到背包中" << endl;
        print_dparr(dp);
    }
1
2
3
4
5
6
7
8

代码运行结果如下：

可以发现结果不一样了，我们只看第一组数据来分析一下产生这种现象的原因，即从物品0中取物品放到背包中得到的结果为

正序遍历的结果：
0 15 30 45 60
倒序遍历的结果：
0 15 15 15 15
1
2
3
4

对比二者可以很容易发现以下现象：

30=15+15
45=30+15
60=45+15
1
2
3

从递推关系式出发：

初始化时dp[0] dp[1] dp[2]均为0,weight[0]=1,value[0]=15。
正序遍历的结果
dp[1] = dp[1 - weight[0]] + value[0] = dp[0] + 15 = 15
dp[2] = dp[2 - weight[0]] + value[0] = dp[1] + 15 = 30
倒序遍历的结果
dp[2] = dp[2 - weight[0]] + value[0] = dp[1] + 15 = 15
dp[1] = dp[1 - weight[0]] + value[0] = dp[0] + 15 = 15
1
2
3
4
5
6
7

下面这段话是理解一维dp数组的核心之处

可以发现正序遍历时计算 dp[2] 时把 dp[1]=15 加上去了，意味着物品0被放入了两次，但实际上加的应该是dp[1]=0 。换种方式理解就是dp[2]的正确计算方式应该是上一行的dp[1]加上15，而如果正序遍历的话，便使得dp[1]的值发生了改变，此时计算的是本行的dp[1]加上15。
因此需要倒序遍历使得每次取得状态不会和之前取得状态重合，这样每种物品就只取一次了。

3.先遍历背包

上述代码及分析均基于先遍历物品，现在分析先遍历背包时的情况。首先从上述分析中我们可以知道，先遍历背包时，二维dp数组是一列一列形成的，但是此时我们用一维dp数组时，我们只能按行形成dp数组，所以只能先遍历物品。

如果非要先遍历背包，可以将上述代码中的循环代码写成如下形式：

  for (int j = bagWeight; j >= 0; j--) {
    for (int i = 0; i < weight.size(); i++) { // 遍历物品
            if (j < weight[i]) continue;
            dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
        }
    	cout << "背包容量为" << j << "时的结果" << endl;
        print_dparr(dp);
    }
1
2
3
4
5
6
7
8

运行结果如下：

首先结果是错误的，这是由于先遍历背包时我们每次只往背包中放入一件物品，所以在背包容量为4时的结果为：
0 0 0 0 30

我们只需要知道先遍历书包跟一维dp数组解决01背包问题的原理相悖，因为根据上述的dp数组形成过程可以知道，先遍历书包的二维dp数组是一列一列往后形成的，而一维dp数组解决01背包问题的原理是由于dp数组可以按行去生成，这两者从本质上就是相悖的，没有讨论的必要。

总结

以上就是我对01背包问题的理解，最核心的地方就是我对每种情况下的01背包问题给出来代码运行结果，便于读者理解。
对于二维dp数组的01背包问题不多赘述，比较好理解。重点在于一维dp数组的01背包问题为什么要倒序遍历背包，以及为什么不能先遍历背包，只能先遍历物品。

1，一维dp数组为什么不能正序遍历书包？
因为正序遍历背包会导致同一个物品被放了两次，但是01背包要求同一物品只能被放一次。

2，一维dp数组为什么不能先遍历背包？
因为能用一维dp数组解决01背包问题的原理就是先遍历物品时dp数组是一行一行形成的（具体过程正文中有结果显示），下一行的数据只受到上一行数据的影响，因此可以只用一维数组去解决01背包问题，但是先遍历书包时dp数组时一列一列形成的（具体过程正文中有结果显示），这二者本质上就是相悖的，如果要强行理解的话，就是如果先遍历背包时，只会往背包中放入一件物品（正文中有具体结果演示）。