辅助理解01背包问题和完全背包问题的优化思想_Java

1、先上代码（Java）

import java.util.Arrays;

public class CompleteBackpack {
    private int[] weight, value; //重量，价值
    private static int cap[];//cap[i]表示可用重量为i时的最大价值
    private int C;//最大容量

    //01背包
    public int knapsack01() {
        int length = weight.length;
        if (length == 0) return 0;
        for (int i = 1; i <= length; i++) {
            for (int j = C; j >=weight[i-1]; j--) { //自顶向下
                cap[j]=Math.max(cap[j], cap[j-weight[i-1]]+value[i-1]);
            }
        }
        return cap[C];
    }

    //完全背包
    public int completeknapsack() {
        int length = weight.length;
        if (length == 0) return 0;
        for (int i = 1; i <= length; i++) {
            for (int j = weight[i-1]; j <= C; j++) { //自底向上
                cap[j] = Math.max(cap[j], cap[j - weight[i-1]]+ value[i-1]);
            }
        }

        return cap[C];
    }

    public void init(int[]  value, int[]  weight,int c) {
        this.weight=weight;
        this.value = value;
        this.C = c;
        cap = new int[c+1];
        Arrays.fill(cap,0);
        
    }

    public static void main(String[] args) {
        int[]  value= {8,5,4,3};
        int[]  weight= {5,4,3,2};
        int c = 10;
        CompleteBackpack knapsack = new CompleteBackpack();
        knapsack.init(value, weight, c);
        System.out.println(knapsack.knapsack01());
        System.out.println(knapsack.completeknapsack());
    }

}

2、完全背包

先分析完全背包是我认为优化后的完全背包比01背包容易理解

完全背包和01背包的这种优化思想是从建表的解法上改进了：表格中下一行的值只跟上一行有关，需要了解演变过程的同学，可以查看这篇文章，下面结合图来分析该优化的思想
优化的解法中，使用一维数组（ private static int cap[ ]）来做存储，其表示的含义是：cap[i]表示可用重量为i时的最大价值，理解这点很重要
下面结合上面代码来介绍

第0层，虚拟的，为第1层做铺垫，全部都初试为0
第1层，即i=1时，对于第二重for循环，j的起点为第1件物品的重量，这里很明显，如果可用重量j低于这件物品的重量，肯定是无法放入背包中。然后在可用重量j从5到9的过程中，最大价值都是8，以j=5时举例，在上一层，即第0层中，可用重量为j时，最大价值为0，即如果不将第1件物品放入背包，那么此时最大价值为0，记为价值A，而如果将第1件物品放入背包中，那么此时最大价值为cap[5 - weight[0]]+ value[0]，即不放入第1件物品时的最大价值+第1件物品的价值，记为价值B，比较A和B，取最大值作为此时可用重量的最大价值。在这里可以看到，当可用重量j为5时，不放入第1件物品的最大价值为cap[0],随着可用重量j的不断增大，直到9，最大价值取得的方式都是0+8，而当j到10，背包中可以容纳两个第1件物品，，此时最大价值变为
cap[10 - weight[0]]+ value[0]=cap[5]+8=8+8=16
这里用到了可用重量为5时的最大价值，即实现了物品的重复使用
此时，内循环完成，得到了当前能够获得的最大价值。
第2层，下面，第2件物品入场了。
依据上面的思路，第2件物品的重量为4，那么可用重量j从4开始，可用得到cap[4]=5，然后继续往下遍历，当可用重量j变为8时，cap[8-weight[1]]+value[1]=5+8=13，与上一层可用重量为8时的最大价值cap[8]=8相比较，更新可用重量为8时的最大价值为13，继续遍历，最后得到如下：
第3层，得到的结果为

5.第4层，得到的结果为

3、 01背包

分析完完全背包，再来看01背包问题就简单了，同样，优化的解法中，使用一维数组（ private static int cap[ ]）来做存储，其表示的含义是：cap[i]表示可用重量为i时的最大价值
01背包与完全背包最大的不同，就是物品不能重复选择，一件物品只能选择一次，所以在更新cap[i]时，就不能像完全背包那样，那么要如何实现在新一轮更新中，即要使用上一轮的结果，又要使得这轮前面更新的结果不会对后面的更新产生影响（即同一个物品重复使用问题）？
答案就是跟完全背包反着来，因为完全的内循环是自底向上，那么反过来就是自顶向下。

第0层，同样，直接初始化为0，为第1层做铺垫
第1层，可用重量j从10开始，逐步减小，直到等于第1件物品的重量（再减小的话，就放不进背包了），以可用重量j=10来举例，上层cap[10]=0，即不放第1件物品的情况，如果要放入的话，那么上一层的最大价值应该是cap[10-5]，放入后，总的最大价值为cap[10-5]+value[0]=0+8=8，比较放跟不放的情况，取最大值，得cap[10]=8。接下来是可用重量j=9，上层cap[9]=0，这是不放第1件物品的情况，如果放入就变成了cap[9-5]+value[0]=8，可得cap[9]=8。同理，可以得到下图的结果，从这个过程中，我们可以发现，在这一轮的更新过程中（或者说一次内循环过程），前面的更新不会影响后面的更新（这里的前面、后面不是指数组cap的前后，而是更新过程的前后，两者是相反的，cap中靠前的元素，是最后更新的），这样一件物品只会被放入一次（是否放入是从cap的值来体现的，完全背包也是一样，因为前面的更新了后面，实现了物品价值的累加）。
第2层，结果如下
第3层，结果如下
第4层，结果如下