关于算法:小白完全背包

在了解齐全背包问题问题之前，必须先深刻理解 01 背包的思路。参考链接：https://blog.csdn.net/qq_4247…

齐全背包的递推关系乍一看与 01 背包大差不差，然而如果不能深刻了解细节，那么在面对口试和面试中的各种齐全背包变形问题时，就会大刀阔斧。

很多人都不会做动静布局问题，我认为所谓触类旁通，就是要形神兼备，不仅仅是记住他的样子，还要深刻思考这个样子的来历，这才是动静布局的真正外延，本人悟明确了，能力在遇到新题的时候应答自若。

最经典的齐全背包问题形容是，有一个限重 W 的背包，有好几种分量为 weight，价值为 value 的物品供你筛选，要在不超过背包限重的前提下，奇妙地抉择物品（每个物品没有数量限度），使得背包外面的物品价值最大。

题目举例：W = 4 weight=[1,3,4] value=[15,20,30]

咱们间接用一维 dp 数组去了解两种背包问题的差别，初始化是全 0 开始，看看第一轮迭代的时候有啥差别。

在 01 背包问题中，当只有 weight[0]=1,value[0]=15 的物品能够抉择时，dp 的第一次迭代是这样的。只有限度 >=1, 因为物品只有一件，所以最大价值都是 15。这就是为什么 01 背包中咱们得倒着遍历。

dp[j] = max(dp[j],dp[j-weight[i]]+value[i]) 当限重为 4 时

dp[4] = max(dp[4],dp[4-weight[0]]+value[0])=max(dp[4],dp[3]+15)=15; 倒着算的话 dp[3]还没算是 0 呢，天然就能失去 15 的正确后果。

而在齐全背包问题中，weight[0]=1,value[0]=15的物品能够抉择屡次，dp 的第一次迭代是这样的。限重 1，2，3，4 别离是 weight[0]的 1234 倍，天然能够失去 15，30，45，60 的价值。那这个时候遍历就得正着来了。

dp[j] = max(dp[j],dp[j-weight[i]]+value[i]) 当限重为 4 时

dp[4] = max(dp[4],dp[4-weight[0]]+value[0])=max(dp[4],dp[3]+15)=60; 正着算的话 dp[3]之前曾经算完了是 45，天然就能失去 60 的正确后果。

遍历形式的不同就解决了物品有一个还是多个的问题，还是很神奇的。其实起因次要是如果正着遍历，前面 dp[j]用到了后面算过的值，那就意味着这个物品不论曾经被拿过了还是没拿过，你这次是新拿的。就像上文 dp[3] = 45, 代表物品拿过了 3 次，你这次还能再拿。

如果还是不够了解，能够从二维 dp 数组的代码解说局部一探到底。

以下代码的精髓所在是二维 dp 数组递推关系的区别。

01 背包的递推关系是

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

齐全背包的递推关系是

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

这里 max 括号的第二项，一个 i，一个 i - 1 就是了解重点所在

i- 1 代表挑了这件物品，就只有 i - 1 件能够挑了
i 代表挑了这件物品，还是有 i 件能够挑，只不过限重变小了而已

#include <iostream>
#include <vector>
using namespace std;
int main(){
    int W = 4;// 限重
    int weight[3] = {1,3,4};// 物品分量
    int value[3] = {15,20,30};// 物品价值
    vector<vector<int>> dp(3,vector<int>(W+1,0)); //3* 5 的 dp
    // 初始化 限重为 0 价值全 0
    // 递推
    for(int i = 0;i < 3;i++){for(int j = 0;j <= W;j++){if(i != 0) dp[i][j] = dp[i-1][j];// 不挑该物品 至多能实现后面 0 -(i-1)件物品的最大价值
            if(j >= weight[i])
                // 挑该物品
                dp[i][j] = max(dp[i][j],dp[i][j-weight[i]]+value[i]);
        }
    }
    // 打印下 dp
    for(int i = 0; i < 3;i++){for(int j = 0;j <=4;j++){cout << dp[i][j] << " ";
        }
        cout << endl;
    }
    cout << dp[2][4];// 最终后果
    return 0;
}

依据二维 dp 中的形容，dp[i] = max(dp[i],dp[i][j-weight[i]]+value[i]), 算以后 dp 须要用到这一行后面的 dp 值，所以一维 dp 遍历的时候只能从前向后遍历了。

所以你看

01 背包的时候要倒序遍历，就怕一维 dp 迭代的时候笼罩了上一轮的值
齐全背包的时候要正序遍历，非得用上后面算的值

#include <iostream>
#include <vector>
using namespace std;
int main(){
    int W = 4;// 限重
    int weight[3] = {1,3,4};// 物品分量
    int value[3] = {15,20,30};// 物品价值
    vector<int> dp(W+1,0); //3* 5 的 dp
    // 初始化 全 0
    // 递推
    for(int i = 0;i < 3;i++){for(int j = 0;j <= W;j++){if(j >= weight[i])
                dp[j] = max(dp[j],dp[j-weight[i]]+value[i]);
        }
    }
    cout << dp[4];// 最终后果
    return 0;
}

关于算法:小白完全背包

齐全背包问题形容与举例

举个例子比照 01 背包和齐全背包在递推关系上的不同

二维 dp 求解齐全背包

手推一下 dp 数组的迭代过程加深了解

一维 dp 的优化