模板

详细解析🔗
完全背包和0-1背包的区分就是物品是否可以被多次选择，再0-1背包的滚动数组中讲过，从后向前遍历背包就是为了防止多次选择物品，所以完全背包就是从前先后选择物品。
先遍历物品：

  1. public static void main(String[] args) {
  2.     int[] weight = {1, 3, 4};
  3.     int[] value = {15, 20, 30};
  4.     int bagsize = 4;
  5.     testweightbagproblem(weight, value, bagsize);
  6. }
  8. public static void testweightbagproblem(int[] weight, int[] value, int bagsize) {
  9.     int[] dp = new int[bagsize + 1];
  10.     for (int i = 0; i < weight.length; i++) {
  11.         for (int j = weight[i]; j <= bagsize; j++) {
  12.             dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
  13.         }
  14.     }
  15.     // 打印dp数组
  16. }

注意物品和背包的遍历可以交换遍历。
先遍历背包：（注意，先遍历背包需要判断背包能否装下商品，或者在物品for循环上做限制）

  1. for (int i = 1; i <= bagWeight; i++){ // 遍历背包容量
  2.     for (int j = 0; j < weight.length; j++){ // 遍历物品
  3.         if (i - weight[j] >= 0){
  4.             dp[i] = Math.max(dp[i], dp[i - weight[j]] + value[j]);
  5.         }
  6.     }
  7. }

在完全背包中，对于一维dp数组来说，其实两个for循环嵌套顺序同样无所谓！
因为dp[j] 是根据 下标j之前所对应的dp[j]计算出来的。 只要保证下标j之前的dp[j]都是经过计算的就可以了。
遍历物品在外层循环，遍历背包容量在内层循环，状态如图：
image.png
遍历背包容量在外层循环，遍历物品在内层循环，状态如图：
image.png
而0-1背包会存在覆盖的问题。