背包问题 0-1背包 完全背包

区分
统一背包问题都先遍历物品（物品重量）再遍历背包（背包大小） 0-1背包问题遍历背包时逆序， 完全背包问题遍历背包时正序 求最大价值，dp初始值就小点（一般0就行），求最小价值，dp初始值就大点（找个数 Interger最大值或者背包大小+1W这种）

0-1背包是 一个背包里每个物品最多能放一次
完全背包是 一个背包里每个物品可以放多次
0-1背包
https://kamacoder.com/problempage.php?pid=1046

public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int M = sc.nextInt();
        int N = sc.nextInt();
        int[] weight = new int[M];
        int[] value = new int[M];
        for (int i = 0; i < M; i++) {
            weight[i] = sc.nextInt();
        }
        for (int i = 0; i < M; i++) {
            value[i] = sc.nextInt();
        }
        int[] dp = new int[N+1];
        //且初始化全是0
        for (int i = 0; i < M; i++) {
            for (int j = N; j >= weight[i] ; j--) {
                dp[j] = Math.max(dp[j],dp[j - weight[i]] + value[i]);
            }
        }
        System.out.println(dp[N]);
    }

总结： dp[j]的含义是 用i以及i以前的物品去放的最大价值 j >= weight[i]说明j容量能放下i物品，那就判断不放i的时候和拿出来一个i的空去放i的时候哪个价值更高。 0-1背包遍历背包时逆序
完全背包
https://kamacoder.com/problempage.php?pid=1052

public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int V = sc.nextInt();
        int[] weight = new int[N];
        int[] value = new int[N];
        for (int i = 0; i < N; i++) {
            weight[i] = sc.nextInt();
            value[i] = sc.nextInt();
        }
        //初始值dp都为0  求最大价值，每一步用max，初始为小点
        int[] dp = new int[V+1];
        for (int i = 0; i < N; i++) {
            for (int j = weight[i]; j <= V ; j++) {
                dp[j] = Math.max(dp[j],dp[j - weight[i]] + value[i]);
            }
        }
        System.out.println(dp[V]);
    }

总结： 完全背包问题，dp[j]代表用i物品以及i之前的物品去放的最大价值，，完全背包，所以遍历背包时正序。