动态规划：01 背包（闫氏DP分析法）

动态规划：01 背包（闫氏DP分析法）

01 背包

www.acwing.com/problem/content/2/

DP:

• 状态表示 f(i, j)​

  • 集合：所有只考虑前 $i$ 个物品，且总体积不超过 $j$ 的选项的集合

  • 属性：max

    • 最终答案：f(N, V)​

• 状态计算：f(i, j) = max(f(i - 1, j), f(i - 1, j - v[i]) + w[i])​

  • 选第 $i$ 个物品：所有包含第 $i$ 个物品的选项集合，其实需要找的就是变化的部分的最大值，即：从 $1$~$i-1$ 中选择，且总体积小于等于 $j-v[i]$ 的选项集合

    当 $j<v[i]$ 时，该分支不存在

    • 变化的部分：包含前 $i-1$ 个物品的不同选项
    • 不变的部分：都需要包含第 $i$ 个物品

  • 不选第 $i$ 个物品：需要满足从 $1$~$i-1$ 中选择，且总体积小于等于 $j$ 的所有选项集合

二维朴素写法

import java.util.*;public class Main {static final int N = 1010;// f[i][j] 表示只对于前i个物品且使用j的背包空间，选取的所有方案中的最大值static int[][] f = new int[N][N];static int[] w = new int[N];static int[] v = new int[N];public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int V = sc.nextInt();for (int i = 1; i <= n; i++) {v[i] = sc.nextInt();w[i] = sc.nextInt();}// dpfor (int i = 1; i <= n; i++) {for (int j = 0; j <= V; j++) {if (j >= v[i]) {// j >= v[i] 能够将第i个物品放入// 放入第i个物品f[i][j] = f[i - 1][j - v[i]] + w[i];}// 不放入第i个物品f[i][j] = Math.max(f[i][j], f[i - 1][j]);}}System.out.println(f[n][V]);}
}

一维优化写法

import java.util.*;public class Main {static final int N = 1010;// 一维优化，相当于每次的i直接覆盖在上一次的i-1数组上// 因为每一次只会用到上一层的，不会用到更上面的数据// 且每次j-v[i]只会用在j之前的，当使用从大到小遍历时，当前修改不会影响到后面的答案// 所以可以使用滚动数组优化static int[] f = new int[N];static int[] w = new int[N];static int[] v = new int[N];public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int V = sc.nextInt();for (int i = 1; i <= n; i++) {v[i] = sc.nextInt();w[i] = sc.nextInt();}// dpfor (int i = 1; i <= n; i++) {// 想清楚为什么要从大到小// 因为遍历到j时要使用上一层的j-v[i]，所以应当先遍历大的才能避免影响for (int j = V; j >= 0; j--) {if (j >= v[i]) {// j >= v[i] 能够将第i个物品放入// 不放入第i个物品, 放入第i个物品f[j] = Math.max(f[j], f[j - v[i]] + w[i]);    }}}System.out.println(f[V]);}
}