动态规划：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();
        }
        
        // dp
        for (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();
        }
        
        // dp
        for (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]);
    }
}