背包理论之01背包

对于面试的话，其实掌握01背包，和完全背包，就够用了，最多可以再来一个多重背包。
背包问题有背包九讲即九个种类的问题

总括：
背包问题即 将n个物品放入容量为 j 的背包中所产生的最大价值。
这个使用动态规划即当前值可由前面值表现出来，具体通过是否将最后一个物品放入到背包中。若放入到背包中此时所产生的最大价值为 前n-1个物品放入到容量为j-weight【n】的背包中所产生的最大价值+第n个物品的价值。若不将最后一个物品放入到背包中，那么此时所产生的最大价值为前n-1个物品放入到容量为 j 的背包中所产生的最大价值。

物品分为：

1. 价值
2. 体积 / 质量
3. 每个物品的数量

01背包应用方面的题目转化为01背包问题。

一：dp数组的含义
dp[i][j]：将第0到 i 个物品放进容量为 j 背包中的最大价值。

二：动态规划所需要的递归公式
通过动态规划的含义即当前值可由前一个值推导出，此时就可以联想到，通过是否将最后一个物品添加到背包中进而实现递归公式。
那么可以有两个方向推出来dp[i][j]即是否将最后一个物品加入到背包中，分为：

1. 不放物品i：dp[ i ][ j ]即：将前 i-1个物品放入大小为 j 的背包中的最大价值。
2. 具体由dp[i - 1][j]推出，即背包容量为j，里面不放物品i的最大价值，此时dp[i][j]就是dp[i - 1][j]。(其实就是当物品i的重量大于背包j的重量时，物品i无法放进背包中，所以被背包内的价值依然和前面相同。)
3. 放物品i：dp[ i ][ j ]即：将前 i-1个物品放入大小为 j -weight[ i ]的背包中的价值加上第 i 个物品的价值。
4. 具体由dp[i - 1][j - weight[i]]推出，dp[i - 1][j - weight[i]] 为背包容量为j - weight[i]的时候不放物品i的最大价值，那么dp[i - 1][j - weight[i]] + value[i] （物品i的价值），就是背包放物品i得到的最大价值

所以递归公式： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
其中在遍历 j 的过程当中需要比较 j 与weight【i】的大小关系

三：dp数组初始化记住图片初始化即可
通过递归公式来判断应该怎样初始化才能达成目的。
i 为物品编号，j 为背包重量，对应图如下：

1. 由递推公式可知，当前值是由dp[i - 1][j]和dp[i - 1][j - weight[i]] 决定的。
2. i 由 i-1 推导出来的，那么当 i -1不越界时即 i = 1即dp【0】，即要知道dp【0】【0~n】所以要初始化dp【0】【0 ~ n】。
3. j 由 j 和 j-weight【i】推导出来，当j-weight【i】不越界时即j-weight【i】 = 0。即dp【0~n】【0】要初始化。
   

2的实现即 i 为0， j 为0~n：将第0个物品放进容量为 j 背包中的最大价值。

for (int j = 0 ; j < weight[0]; j++) {  
// 当然这一步，如果把dp数组预先初始化为0了，这一步就可以省略，但很多同学应该没有想清楚这一点。
    dp[0][j] = 0;
}
for (int j = weight[0]; j <= bagweight; j++) {
    dp[0][j] = value[0];
}
1
2
3
4
5
6
7

3的实现即i为0~n，j 为0：将第0 ~n个物品放进容量为0背包中的最大价值（自然是0）
代码省略。

实现2,3的代码：
首先全部初始化为0，然后将实现2，3过程中不应该赋值为0的重新赋值，即如图的部分。

vector<vector<int>> dp(weight.size(), vector<int>(bagweight + 1, 0));

for (int j = weight[0]; j <= bagweight; j++) {
    dp[0][j] = value[0];
}
1
2
3
4
5

四：确定遍历顺序：怎样来实现当前值的前一个值始终已知。其中在遍历 j 的过程当中需要比较 j 与weight【i】的大小关系
由递归公式可知，从图中看来当前值由上方一个值和左上方一个值来决定。可以举例想象一下遍历过程，然后知道既可以一行一行的遍历，在某一行中从前到后遍历，然后再遍历下一行。也可以一列一列的遍历，在某一行中从上到下遍历，然后再遍历下一列。

j为0的时候不论i为多少价值不都是0吗？为什么还要遍历？

先遍历背包，再遍历物品即纵向遍历 j 递增（此为图形理解并非按照for循环的顺序理解）的代码：

// 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]);

    }
}
1
2
3
4
5
6
7
8

先遍历物品，然后遍历背包重量即横向遍历 i 递增（此为图形理解并非按照for循环的顺序理解）的代码：

// weight数组的大小 就是物品个数
for(int j = 0; j <= bagweight; j++) { // 遍历背包容量
    for(int 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]);
    }
}
1
2
3
4
5
6
7

完整c++测试代码

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数组的大小 就是物品个数
    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 << dp[weight.size() - 1][bagweight] << endl;
}

int main() {
    test_2_wei_bag_problem1();
}
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