动态规划/背包问题总结/小结——01背包、完全背包

前言

背包问题也属于动态规划问题。

动态规划就是将复杂的大问题转化为一个小问题，然后将小问题转化为更小的容易求解的问题；通过将最小的容易求解的问题求解，进而一步步推导、求解出最后的结果。

背包问题分类：

动态规划五步法

1. 确定dp数组的含义
2. 确定递推公式
3. 确定初始值
4. 确定遍历顺序
5. 手动推导dp数组的值，是否和程序结果一直

01背包模型

背包的容量为15kg，物品0~4的重量和价值分别为如图所示。
问背包能背的物品最大价值是多少？

每一件物品其实只有两个状态，取或者不取，那么暴力法时间复杂度为O(2^n)。

1. 确定dp数组的含义

dp[i][j]，当背包容量为j时，前 i+1 个物品参与放入背包，此时背包能背的物品的最大价值

2. 确定递推公式

背包容量是个常量。当物品 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，本题对遍历顺序没有特别的要求

5. dp数组

程序示例

    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];
        }
    }
    //根据递推公式计算dp
    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，所以可以降二维dp降为一维度。
   此时dp[j]的含义为容量为j的背包能背物品的最大价值。
2. 递推公式变为：dp[j] = max(dp[j], dp[j-wi]+vi)
3. dp数组初始化，全都为0就行
4. 遍历顺序就有了要求，物品i在外部循环，背包的容量j在内部循环。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);
    // 以下for循环的遍历顺序及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]);
        }
    }
    for (auto c:dp){
        cout << c<< " ";
    }

备注
关于4.一维dp数组的遍历顺序大有讲究，可仔细研究。
当先遍历背包后遍历物品时（j从大到小，i从小到大），每个dp[j]就只会放入一个物品。
当先遍历物品再遍历背包（i从小到大，j从小到大），dp[j]中同一个物品会被放入多次，不符合01背包原则。

完全背包

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

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

例如：

1. dp[j]代表容量为j的背包能背物品的最大价值
2. dp[j] = max(dp[j], dp[j-wi]+vi)
3. 对于此题初始化为0就好
4. 对于遍历顺序可小讨论下。完全背包就是物品可重复放入背包，因此遍历顺序为先遍历物品（i有小到大），再遍历背包（j由小到大）。
   其实，先遍历背包再遍历物品也可。
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]);
        }
    }

总结

01背包模型是所有背包问题的基础。后面的完全背包，多重背包，都是在透彻理解01背包之后的进一步分析，理解了01背包，完全背包、多重背包就非常容易理解。

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

遍历顺序：

总结2

每件物品只有一个
背包能装的物品的总价值的最大值为多少?
vector<int> dp[j]; 背包容量为j时，背包能装的总价值最大为dp[j]
递推公式：dp[j] = max(dp[j], dp[j -w[i]] + v[i])
（物品i不放入背包时的最大价值为dp[j], 物品i放入背包时的最大价值为dp[j-w[i]+v[i]）比较一下放入该物品和不放入该物品哪个价值更大。如果想放入物品i，首先需要为该物品腾出空间j-w[i]然后加上该物品的价值就是放入该物品后的价值。由于是只有一个物品，所以要

// dp[j]价值最大
for (int i=0; i < size; ++i){
  for (int j=bgw; j >= w[i]; --j) {  //背包从大到小遍历
    dp[j] = max(dp[j], dp[j-w[i] + v[i]);//此时背包[j-w[i]]肯定没有放入过物品i
  }
}

完全背包，每件物品有无数个，背包物品的最大价值

// dp[j]价值最大
for (int i=0; i < size; ++i){
  for (int j=0; j <= bgw; ++j) {  //背包从小到大遍历
    dp[j] = max(dp[j], dp[j-w[i] + v[i]);  // 此时背包[j-w[i]]已经放入过物品i了，
    									// 再此放入物品i意味着物品i有无数个
  }
}

每件物品有无数个，有多少种装满背包的方式

// 组合问题，[1 2]和[2 1]属于同一种方式
for (int i=0; i < size; ++i) {     // 先遍历物品
  for (int j = 0; j <= bgw; ++j){  // 再遍历背包
  								  // 组合问题，[1，2]和[2，1]属于一种可能
  					// 当遍历到物品2时，只可能出现[1 2]的解，不可能出现物品2在最前面的解[2 1]
    dp[j] = (dp[j]） +  ( dp[j-w[i]] );
    // 本次不放入物品i有dp[j]个方式，确认放入i有dp[j-w[i]]种方式，放和不放相加就是总共的dp[j]的组合数
  }
}


// 排列问题, [1 2]和[2 1]属于两种方式
for (int j = 0; j <= bgw; ++j){
  for (int i = 0; i < size; ++i){
    dp[j] = (dp[j]) + ( dp[j-w[i]] );
  }
}

装满背包的组合的元素的个数最少、最大

// 因为是元素个数，所以对组合还是排列无要求
min(dp[j], dp[j-w[i]]+1);
max(dp[j], dp[j-w[i]]+1);
// 物品i不放入时的元素个数为dp[j]
// 物品i放入时的元素个数为 dp[j-w[i]] + 1