本文參考:動態(tài)規(guī)劃：關(guān)于完全背包易结，你該了解這些！
1练对、問題定義
上一節(jié)，我們介紹了0-1背包痢法，每種物品只有一件時柴钻，背包能裝的最大價值。本節(jié)货葬，我們討論當每種物品的數(shù)量不限（也就是可以放入背包多次）時采幌，背包能裝的最大價值。
2震桶、遍歷順序
0-1背包和完全背包唯一不同就是體現(xiàn)在遍歷順序上休傍，所以本文就不去做動規(guī)五部曲了，我們直接針對遍歷順序經(jīng)行分析蹲姐！
首先磨取，我們回顧一下，用滾動數(shù)組實現(xiàn)的01背包
for(int i = 0; i < weight.size(); i++) { // 遍歷物品
for(int j = bagWeight; j >= weight[i]; j--) { // 遍歷背包容量
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}
}
01背包內(nèi)嵌的循環(huán)是從大到小遍歷柴墩，為了保證每個物品僅被添加一次忙厌。當從小到大遍歷時，同一個物體會被添加多次江咳，這不正是完全背包需要的嗎逢净？！
完全背包的物品是可以添加多次的，所以要從小到大去遍歷爹土，即：
// 先遍歷物品甥雕，再遍歷背包
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]);
}
}
三、內(nèi)外循環(huán)
其實還有一個很重要的問題胀茵，為什么遍歷物品在外層循環(huán)社露，遍歷背包容量在內(nèi)層循環(huán)？
這個問題大家都默認遍歷物品在外層琼娘，遍歷背包容量在內(nèi)層峭弟，好像本應(yīng)該如此一樣，那么為什么呢轨奄？
01背包中二維dp數(shù)組的兩個for遍歷的先后循序是可以顛倒了孟害，一位dp數(shù)組的兩個for循環(huán)先后循序一定是先遍歷物品，再遍歷背包容量挪拟。
在完全背包中挨务，對于一維dp數(shù)組來說，其實兩個for循環(huán)嵌套順序同樣無所謂！
因為dp[j] 是根據(jù) 下標j之前所對應(yīng)的dp[j]計算出來的。只要保證下標j之前的dp[j]都是經(jīng)過計算的就可以了抗楔。
遍歷物品在外層循環(huán)，遍歷背包容量在內(nèi)層循環(huán)朝巫，狀態(tài)如圖：
遍歷背包容量在外層循環(huán)，遍歷物品在內(nèi)層循環(huán)石景，狀態(tài)如圖：
看了這兩個圖劈猿，大家就會理解，完全背包中潮孽，兩個for循環(huán)的先后循序揪荣，都不影響計算dp[j]所需要的值（這個值就是下標j之前所對應(yīng)的dp[j]）。
最后往史，又可以出一道面試題了仗颈，就是純完全背包，要求先用二維dp數(shù)組實現(xiàn)椎例，然后再用一維dp數(shù)組實現(xiàn)挨决，最后在問，兩個for循環(huán)的先后是否可以顛倒订歪？為什么脖祈？這個簡單的完全背包問題，估計就可以難住不少候選人了刷晋。
