完全背包问题

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

相较于0/1背包问题，完全背包问题最大的不同之处在物品的个数是无限。那么在进行选择时，就是每一次向背包中添加物品时，都有 n 个物品可供选择。

假设背包的容量为4，重量和价值数组分别为： weight={1,3,4},value={15,20,30}

此时需要求解背包能够装下的最大价值的物品。

多重背包问题的关键：在于对于每一个物体可以选择多次，在基于滚动数组的实现中，为了避免重复选择同一元素，在对背包的内层循环过程中采取从右向左的方式。那么在完全背包中要实现重复选择只需要将背包的内层循环从左向右进行即可。

动态规划数组的定义：定义数组 dp[W+1] 表示，容量为 W 的背包能够装下的物品的最高价值。
动态规划数组的推导：每次尝试将元素 i 转入到背包中看能否使得价值上升 dp[j]=max(dp[j],dp[j-weight[i]]+value[i])
动态规划数组的初始化：初始时，未将物品装入到背包中，背包中的价值全部为 0
动态规划数组的遍历顺序：在内外层循环中，既可以先遍历物品也可以先遍历背包，但是不论是对物品还是背包容量的遍历都需要从前向后进行。对于先遍历物品再遍历背包的理解：不断增加背包可选择的物品，在每一次添加物品后可以选择0或n个当前物品，将全部的物品都考虑到之后所得就是当前背包能够得到的最有化解。对于先遍历背包再遍历物品的理解：不断增加的是背包的容量，对于每一个背包容量，求解的是小容量的完全背包问题。（本质上就是一个减少物品的个数，一个减少背包的容量，从两个角度去划分子问题）

先遍历物品，再遍历背包的代码实现：

vectr<int> dp(W+1,0);
for(int i=0;i<value.size();i++){
    for(int j=weight[i];j<=W;j++){ // 此处需要从weight[i]开始
        dp[j]=max(dp[j],dp[j-weight[i]]+value[i]);
    }
}

先遍历背包再遍历物品的代码实现：

vectr<int> dp(W+1,0);
for(int j=0;j<=W;j++){
    for(int i=0;i<weight.size();i++){
        dp[j]=j>=weight[i]?max(dp[j],dp[j-weight[i]]+value[i]):dp[j];
    }
}