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

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

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

齐全背包问题形容与举例

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

题目举例：W = 4 weight=[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,代表物品拿过了3次，你这次还能再拿。

如果还是不够了解，能够从二维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>
#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的优化

依据二维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;
}