完整背包细节与完整背包问题说明实例比较求解01背包与完整背包递归关系不同的二维dp手按完整背包了解dp序列迭代过程深化一维dp优化
在理解完整的背包问题之前，必须深入理解01背包的思路。 参考链接：链接：零度基点01背包问题有诀窍。
完全背包的递归关系乍一看与一背包相差不大，但如果不能深入理解细节，面对笔试和面试中各种完全背包的变形问题时，就会束手无策。
很多人不做动态规划问题。 举一反三，我认为是形与神兼具。 不仅要记住他的样子，还要深刻思考他的来历，这才是动态规划的真谛，只有自己领悟和理解，才能在遇到新问题时更容易应对。
完全背包问题的说明和作为例子最典型的完全背包问题的说明是，有重量限制的w背包，一些重量为weight，价值为value的物品是为你选择的。 为了不超过背包的重量限制，要巧妙地选择物品，使背包中物品的价值最大化。
主题： w=4weight=[ 1，3，4 ] value=[ 15，20，30 ]举个例子，比较01背包与完全背包递归关系的差异，直接用一维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，代表性的东西我拿过三次，但这次又可以拿了。
如果仍然不够理解，请从二维dp数组的代码说明部分开始调查。
二维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 # includevectorusingnamespacestion int main () intw=4； //重量限制int weight [3]={ 1，3，4 }； //物品重量intvalue [3]={ 15，20，30 }； //物的价值vectorvectorintDP(3，vectorint ) w1，0 )； //3*5的dp //初始化限制为0价值全0 //递归for(intI=0； i 3； I ) for(intj=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 ] i 3； I ) for(intj=0； j=4； j({coutDP[I][j] '； } cout endl； } cout dp[2][4]； //最终结果return 0； }手按DP序列迭代过程加深理解
根据二维dp中的描述，一维dp优化为dp[i]=max(dp[i]，dp[i][j-weight[i]] value[i] )，计算出当前dp需要使用此行中的上一个dp值
所以请看
01背包时反向遍历的方法是：一维dp迭代时覆盖前一回合的值，完全背包时正向遍历，而之前计算出的值# include iostream # includevectorusingnamesparam int main () intw=4； //重量限制int weight [3]={ 1，3，4 }； //物品重量intvalue [3]={ 15，20，30 }； //物的价值vectorintdp (w1，0 )； //3*5的dp //初始化全0 //递归for(intI=0； i 3； I ) for(intj=0； j=W； j () if(j=weight[I] ) DP )=max ) DP[j]，DP[j-weight[I] ) value[I] )； } } cout dp[4]； //最终结果return 0； }