知识点补充

背包问题
    1. 01背包 物品只能用0 1次
    2. 完全背包 物品可以无限用
    3. 多重背包 物品只能用s[i]次
    4. 分组背包 每组只能选一个
   本质就是N个物品，包的体积是V，每个物品的体积是v[i]，价值是w[i]，求不超过V的最大价值

DP问题思路
   1. 状态表示
        集合
           包含所有选法的集合
    01 的选法就是从i之前包含i选择总体积小于V的
        属性
           max min  数量
   2. 状态计算
        划分集合
    不包含i和包含i
                f[i][j] = max(f[i - 1][j], f[i-1][j - v[i]] + w)


DP优化就是二维转一维，优化状态转移方程

题目描述

01背包问题

输入样例

4 5
1 2
2 4
3 4
4 5

输出样例

8

算法1

(DP) $O(n^2)$

blablabla

时间复杂度

参考文献：y总

Java 代码

二维

import java.util.Scanner;

/**
 * 01背包问题
 */
public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        String[] s = scan.nextLine().split(" ");
        int N = Integer.parseInt(s[0]);// N件物品
        int V = Integer.parseInt(s[1]);// V总体积
        int[] v = new int[N + 1];// 存放每个物品的体积
        int[] w = new int[N + 1];// 存放每个物品的权重
        for (int i = 1; i <= N; i ++){
            s = scan.nextLine().split(" ");
            v[i] = Integer.parseInt(s[0]);
            w[i] = Integer.parseInt(s[1]);
        }

        // f[2][3] 表示 当前情况中最多选中两件物品，体积不超过3的 Max权重
        int[][] f = new int[N + 1][V + 1];
        // 主要工作就是 分别选择1-N个物品，在体积不超过j的最大值 最后赋值给f[i][j]
        for (int i = 1; i <= N; i++){// 从选1个到选N个
            for (int j = 0; j <= V; j++){// 每次从0-V遍历哪个体积最大
                if (j >= v[i]){
                    f[i][j] = Math.max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);
                }else{
                    f[i][j] = f[i - 1][j];
                }
            }
        }
        System.out.println(f[N][V]);
    }
}

一维（优化）

import java.util.Scanner;

/**
 * 01背包问题
 */
public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        String[] s = scan.nextLine().split(" ");
        int N = Integer.parseInt(s[0]);// N件物品
        int V = Integer.parseInt(s[1]);// V总体积
        int[] v = new int[N + 1];// 存放每个物品的体积
        int[] w = new int[N + 1];// 存放每个物品的权重
        for (int i = 1; i <= N; i ++){
            s = scan.nextLine().split(" ");
            v[i] = Integer.parseInt(s[0]);
            w[i] = Integer.parseInt(s[1]);
        }

        // f[2][3] 表示 当前情况中最多选中两件物品，体积不超过3的 Max权重
        int[] f = new int[V + 1];
        // 主要工作就是 分别选择1-N个物品，在体积不超过j的最大值 最后赋值给f[i][j]
        for (int i = 1; i <= N; i++){// 从选1个到选N个
            for (int j = V; j >= v[i]; j--){
                // j 从大到小遍历 因为如果从小到大遍历 每次更新f[j]的时候都会用到小的f[j-v[i]],
                // 但是f[j-v[i]]是已经更新过的肯定是第i层，原始原方程是i-1层,不匹配!
                // 如果从大到小遍历，每次用的都是没有跟新过的即i-1层 跟原方程匹配
                // 不是很理解 等日后再来看
                f[j] = Math.max(f[j], f[j - v[i]] + w[i]);
            }
        }
        System.out.println(f[V]);

    }
}