完全背包

有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品都有无限个（也就是可以放入背包多次），求解将哪些物品装入背包里物品价值总和最大。

完全背包和01背包问题唯一不同的地方就是，每种物品有无限件。

例子

背包最大重量为4。

每件商品都有无限个，问背包能背的物品最大价值是多少？

分析

01背包和完全背包唯一不同就是体现在遍历顺序上。

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]);
    }
}

一维dp遍历的时候，背包是从大到小。倒叙遍历每次取得状态不会和之前取得状态重合，保证物品i只被放入一次。

完全背包的物品是可以添加多次的，所以要从小到大去遍历:

// 先遍历物品，再遍历背包
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]);
    }
}

遍历循序

01背包中二维dp数组的两个for遍历的先后循序是可以颠倒的，二一维dp数组的两个for循环先后循序一定是先遍历物品，再遍历背包容量。

在完全背包中，对于一维dp数组来说，两个for循序却是可以颠倒的。因为dp[j] 是根据下标j之前所对应的dp[j]计算出来的，只要保证下标j之前的dp[j]都是经过计算的就可以了。

遍历物品在外层循环，遍历背包容量在内层循环：

遍历背包容量在外层循环，遍历物品在内层循环：

先遍历背包再遍历物品代码：

// 先遍历背包，再遍历物品
for(int j = 0; j <= bagWeight; j++) { // 遍历背包容量
    for(int i = 0; i < weight.size(); i++) { // 遍历物品
        if (j - weight[i] >= 0) dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
    }
}

动态规划：完全背包