Dynamic Programming/Knapsack Problem Summary/Summary - 01 Knapsack, Complete Knapsack

---

前言

The knapsack problem is also a dynamic programming problem.

Dynamic programming is all about transforming a big, complex problem into a small problem,Then turn small problems into smaller, easier-to-solve problems;By taking the smallest easy-to-solve problem to solve,Further derivation step by step、Solve for the final result.

背包问题分类：

---

Five-step method of dynamic programming

1. 确定dp数组的含义
2. 确定递推公式
3. 确定初始值
4. 确定遍历顺序
5. 手动推导dp数组的值,Whether it is consistent with the program results

01背包模型

背包的容量为15kg,物品0~4The weight and value respectively are as shown.
问背包能背的物品最大价值是多少？

项目	Value	Weight
物品0	$4	12kg
物品1	$2	1kg
物品2	$10	4kg
物品3	$1	1kg
物品4	$2	2kg

每一件物品其实只有两个状态,取或者不取,Then the time complexity of the brute force method is O(2^n).

1. 确定dp数组的含义

dp[i][j],当背包容量为j时,前 i+1 Participate in putting items into the backpack,The maximum value of the items that the backpack can carry at this time

2. 确定递推公式

Backpack capacity is a constant.当物品 i 不放入背包时 dp[i][j] = dp[i-1][j];当物品 i 放入背包时dp[i][i] = dp[i-1][j-wi] + vi;
所以 dp[i][j] = max( dp[i-1][j], dp[i-1][j-wi]+vi )

3. 确定初始值

根据递推公式,需要确定i=0和j=0时的初值

4. 确定遍历顺序

根据5,This question has no special requirements on the traversal order

5. dp数组

	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
物品0	0	0	0	0	0	0	0	0	0	0	0	0	4	4	4	4
物品1	0	2	2	2	2	2	2	2	2	2	2	2	4	6	6	6
物品2	0	2	2	2	10	12	12	12	12	12	12	12	12	12	12	12
物品3	0	2	3	3	10	12	13	13	13	13	13	13	13	13	13	13
物品4	0	2	3	4	10	12	13	14	15	15	15	15	15	15	15	15

程序示例

    vector<int> w = {
    12,1,4,1,2};
    vector<int> v = {
    4,2,10,1,2};
    int begWight = 15;
    vector<vector<int>> dp(w.size(), vector<int>(begWight+1, 0));
    for (int j=0;j<=begWight; ++j){
     //dp数组初始化
        if (w[0] <= j){
    
            dp[0][j] = v[0];
        }
    }
    //Calculated according to the recursive formuladp
    for (int i=1; i<w.size(); ++i){
    
        for (int j=1; j<=begWight; ++j){
    
            if (j<w[i]) 
                dp[i][j] = dp[i-1][j];
            else 
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]]+v[i]);
        }
    }
    //打印dp
    for (int i=0; i<dp.size(); ++i){
    
        for (int j=0; j<dp[0].size(); ++j){
    
            cout << dp[i][j] << " ";
        }
        cout << endl;
    }

优化dp的维度

1. 根据递推公式dp[i][j] = max( dp[i-1][j], dp[i-1][j-wi]+vi ),i取决于i-1,So it can be reduced to two dimensionsdpdown to one dimension.
   此时dp[j]means the capacity is jThe backpack can carry the maximum value of the item.
2. The recursion formula becomes：dp[j] = max(dp[j], dp[j-wi]+vi)
3. dp数组初始化,全都为0就行
4. Traversal order is required,物品i在外部循环,背包的容量jloop inside.j从大到小

for (int i=0; i<w.size(); ++i){
                  //先遍历物品
    for (int j=begWight; j>=w[i]; --j){
          //再遍历背包
        dp[j] = max(dp[j], dp[j-w[i]]+v[i]);
    }
}

5. dp数组
   当i=0; dp 0 0 0 0 0 0 0 0 0 0 0 0 4 4 4 4
   当i=1; dp 0 2 2 2 2 2 2 2 2 2 2 2 4 6 6 6
   当i=2; dp 0 2 2 2 10 12 12 12 12 12 12 12 12 12 12 12
   当i=3; dp 0 2 3 3 10 12 13 13 13 13 13 13 13 13 13 13
   当i=4; dp 0 2 3 4 10 12 13 14 15 15 15 15 15 15 15 15

代码示例

    vector<int > dp(begWight+1, 0);
    // 以下forThe traversal order of the loop andj的顺序不能变,Think about what would happen if it changed
    for (int i=0; i<w.size(); ++i){
                   //先遍历物品
        for (int j=begWight; j>=w[i]; --j){
           //再遍历背包,从大到小
            dp[j] = max(dp[j], dp[j-w[i]]+v[i]);
        }
    }
    for (auto c:dp){
    
        cout << c<< " ";
    }

备注
关于4.一维dpThe order in which the array is traversed is very particular,can be carefully studied.
When traversing the backpack first and then traversing the items（j从大到小,i从小到大）,每个dp[j]就只会放入一个物品.
When traversing items first and then traversing the backpack（i从小到大,j从小到大）,dp[j]The same item will be placed multiple times,不符合01Backpack principle.

完全背包

有N件物品和一个最多能背重量为W的背包.第i件物品的重量是weight[i],得到的价值是value[i] .每件物品都有无限个（也就是可以放入背包多次）,求解将哪些物品装入背包里物品价值总和最大.

完全背包和01背包问题唯一不同的地方就是,每种物品有无限件.

例如：

	W	V
物品0	1	15
物品1	3	20
物品2	4	30

1. dp[j]代表容量为jThe backpack can carry the maximum value of the item
2. dp[j] = max(dp[j], dp[j-wi]+vi)
3. Initialize for this question0就好
4. The traversal order can be discussed briefly.A full backpack is one where items can be put into the backpack repeatedly,So the traversal order is to traverse the items first（i有小到大）,再遍历背包（j由小到大）.
   其实,It is also possible to traverse the backpack first and then traverse the items.
5. 略

程序示例

    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 = weight[i]; j <= bagWeight; j++) {
     // 遍历背包容量
            dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
        }
    }

---

总结

01The knapsack model is the basis for all knapsack problems.Complete backpack at the back,多重背包,are fully understood01Further analysis after the backpack,理解了01背包,完全背包、Multiple backpacks are very easy to understand.

递推公式：
背包总价值：dp[j] = max(dp[j], dp[j - w[i]] + v[i])
装满背包：dp[j] += dp[j - nums[i]]

遍历顺序：

	01背包	完全背包
顺序问题	There is only one order,先遍历物品（from to large）再遍历背包（There are big to small）	先遍历物品（由小到大）再遍历背包（有小到大）,In fact, the reverse is also possible