昨天动态规划：关于01背包问题，你应该知道这个！01背包用二维dp数组来解释。今天我们就来说说滚动数组。其实我们在上一个题目中已经用到了rollingarrays，就是把二维的dp降为一维的dp。一些记录员当时表示很困惑。那我们就通过01背包把滚动阵说个透彻吧！接下来我们用下面的例子来说明背包的最大重量是4。物品是：背包可以携带的物品的最大价值是多少？一维的dp数组（滚动数组）对于背包问题其实是可压缩的。当使用二维数组时，递推公式：dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i]);其实可以发现，如果把dp[i-1]的层复制到dp[i]，表达式可以是：dp[i][j]=max(dp[i][j],dp[i][j-权重[i]]+值[i]);与其将dp[i-1]这一层复制到dp[i]，不如只用一个一维数组，直接用dp[j]即可（一维数组，也可以理解为滚动数组).这就是滚动阵的由来。需要满足的条件是前一层可以复用，直接复制到当前层。看完这里，我想大家已经忘记了dp[i][j]中的i和j表达的是什么。i是物品，j是背包容量。dp[i][j]表示从下标为[0-i]的物品中任意取出，放入容量为j的背包中。值的最大总和是多少。一定要时刻记住这里i和j的意思，否则很容易混淆。动态规则的五个部分分析如下：1.确定dp数组的定义在一维dp数组中，dp[j]表示：一个容量为j的背包，可以携带的物品其价值可以取决于dp[j]。2、一维dp数组的递推公式dp[j]是一个容量为j的背包携带的最大值，那么dp[j]如何推导呢？dp[j]可以通过dp[j-weight[i]]推导出来，dp[j-weight[i]]表示一个容量为j-weight[i]的背包携带的最大值。dp[j-weight[i]]+value[i]表示背包的容量为j-第i项的重量加上第i项的价值。（即容量为j的背包，放入物品i后的价值：dp[j]）此时dp[j]有两种选择，一种是取自己的dp[j]，即相当于二维dp数组dp[i-1][j]，即不放第i项，一个是取dp[j-weight[i]]+value[i]，即，放第i项，指定的是取最大的，毕竟是最大值，所以递归公式为：dp[j]=max(dp[j],dp[j-weight[i]]+值[i]);可以看出，相对于二维dp数组，去掉了dp[i][j]中i的维度。3、如何初始化一维dp数组关于初始化，一定要和dp数组的定义保持一致，否则到递归公式的时候会越来越乱。dp[j]的意思是：对于一个容量为j的背包，携带物品的最大值可以为dp[j]，那么dp[0]应该为0，因为背包携带的物品最大值为dp[j]，那么dp[0]应该为0acapacity为0即为0，那么dp数组除了下标0的位置外都初始化为0，还有多少个下标要初始化呢？看递推公式：dp[j]=max(dp[j],dp[j-weight[i]]+value[i]);dp数组必须是推导时取最大值的数。如果题目给的值都是正整数，那么就可以把所有非零下标都初始化为0。这样在递归公式的时候dp数组就可以取最大值，而不是被初始覆盖价值。那么我假设items的值都大于0，所以在初始化dp数组的时候，初始化为0就可以了。4、遍历一维dp数组的代码如下：for(inti=0;i=weight[i];j--){//遍历背包容量dp[j]=最大值（dp[j]，dp[j-权重[i]]+值[i]）；}}到这里，大家发现在二维dp的写法中，遍历背包的顺序是不一样的！遍历二维dp时，背包容量由小到大，而遍历一维dp时，背包容量由大到小。为什么？逆序遍历是为了保证第i项只被放入一次！。但是一旦正序被遍历，那么item0就会被多次添加！例如：item0的权重weight[0]=1，value值value[0]=15如果正序遍历dp[1]=dp[1-weight[0]]+value[0]=15dp[2]=dp[2-weight[0]]+value[0]=30此时dp[2]已经是30，说明item0已经被放入了两次，所以不能正序遍历。为什么要倒序遍历保证item只放一次？逆序计算dp[2]dp[2]=dp[2-weight[0]]+value[0]=15（dp数组已经初始化为0）dp[1]=dp[1-weight[0]]+value[0]=15这样从后往前循环，每次得到的状态都不会和之前得到的状态重合，这样每个item只取一次。那么问题又来了，为什么二维dp数组日历不是倒序的呢？因为对于二维dp来说，dp[i][j]是通过上一层计算出来的，即dp[i-1][j]，这一层的dp[i][j]不会被覆盖！（这里如果看不懂，还得自己去试试，空想还是靠不住的，真知灼见实践出来！）我们来看看这两个for循环嵌套的顺序，在代码中，是嵌套遍历item，先遍历背包容量，那么是否可以先遍历背包容量，再嵌套遍历item？不！因为是一维dp的写法，背包容量必须倒序遍历（原因上面已经说过），如果遍历背包容量放在上层，那么每个dp[j]只会放一个item，即：背包里只放一件物品。（如果这里不明白，就回忆一下dp[j]的定义，或者把两个for循环的顺序倒过来试试！）所以一维dp数组的knapsack的遍历顺序其实和那个有很大的不同二次元的大不同！每个人都必须注意这一点。5、例如推导dp数组的一维dp，分别用item0、item1、item2遍历背包，最终得到如下结果：动态规划-背包问题9一维dp01背包完整的C++测试代码voidtest_1_wei_bag_problem(){vectorweight={1,3,4};向量值={15,20,30};intbagWeight=4;//初始化向量dp(bagWeight+1,0);for(inti=0;i=weight[i];j--){//遍历背包容量dp[j]=max(dp[j],dp[j-weight[i]]+value[i]);}}cout<=weight[i];j--){dp[j]=Math.max(dp[j],dp[j-weight[i]]+value[i]);}}//打印dp数组for(intj=0;j<=bagWeight;j++){System.out.print(dp[j]+"");}}Pythondeftest_1_wei_bag_problem():weight=[1,3,4]value=[15,20,30]bag_weight=4#初始化：全0dp=[0]*(bag_weight+1)#先遍历items，再穿越背包容量foriinrange(len(weight)):forjinrange(bag_weight,weight[i]-1,-1):#递归公式dp[j]=max(dp[j],dp[j-weight[i]]+value[i])print(dp)test_1_wei_bag_problem()Gofunctest_1_wei_bag_problem(weight,value[]int,bagWeightint)int{//定义并初始化dp:=make([]int,bagWeight+1)//i的递归顺序:=0;i=重量[i];j--{//递归公式dp[j]=max(dp[j],dp[j-weight[i]]+value[i])}}//fmt.Println(dp)returndp[bagWeight]}funcmax(a,bint)int{ifa>b{returna}returnb}funcmain(){weight:=[]int{1,3,4}value:=[]int{15,20,30}test_1_wei_bag_problem(weight,value,4)}javaScriptfunctiontestWeightBagProblem(weight,value,size){constlen=weight.length,dp=Array(size+1).fill(0);for(leti=1;i<=len;i++){for(letj=size;j>=weight[i-1];j--){dp[j]=Math.max(dp[j],值[i-1]+dp[j-w右[i-1]]);}}returndp[size];}functiontest(){console.log(testWeightBagProblem([1,3,4,5],[15,20,30,55],6));}test();
