题解 | 0-1 背包问题

什么叫01背包？

• 题目会给与一个背包的容积，以及几个物品和该物品的体积与价值，问背包最多能装多大价值。
• 每个物品只能拿一次，拿就是1，不拿就是0。 所以这一类动态规划的问题叫做01背包问题。

核心代码：

//用体积数作为下标, 可以找到体积数对应的价值
        int[] dp1 = new int[V+1];
        int[] dp2 = new int[V+1];
        Arrays.fill(dp2, Integer.MIN_VALUE); //用来区分放了东西价值为零, 还是没放东西
        dp2[0] = 0;
        //物品遍历
        for (int i = 0; i < n; i++) {
            for (int j = V; j >= v[i]; j--){
                dp1[j] = Math.max(dp1[j], dp1[j-v[i]]+w[i]);
                dp2[j] = Math.max(dp2[j], dp2[j-v[i]]+w[i]);
            }
           
        }
        System.out.println(dp1[V]);
        System.out.println(dp2[V] < 0 ? 0 : dp2[V]);

算法流程

1. 设定两个数组，以体积为下标分别用来记录局部最优解和恰好满背包最优解。
2. 设定两个for循环，外循环用来遍历物品，内循环用来遍历背包容积——从最大容积到能装下当前物品的最小容积。
3. 内循环判断当前容积下最优解与插入当前物品后最优解大小，取最大一方做新的局部最优解（解决装不装的问题）； 内循环判断当前容积下是否能整装当前物品，并记录最优解。
4. 输出最优解

dp1与dp2分别是干什么的？

dp1：存储在不同背包容积下塞入当前物品的价值最优值

 dp1[j] = Math.max(dp1[j], dp1[j-v[i]]+w[i]);

• dp1的每一项记载的都是不同容积下的物品价值最优值。
• 从算法可看出j代表的能装的下i物品的容积，计算最优值时，判断塞入i之前的当前容积的最优价值dp1[j]与塞入i物品后的最优价值（dp1[j-v[i]]+w[i]所剩容积的最优价值加i物品的价值），谁大就意味着谁是最优解，将最优解刷新至dp1[j]。

dp2：存储不同背包容积下正好塞满的价值最优值

dp2[j] = Math.max(dp2[j], dp2[j-v[i]]+w[i]);

dp2首位赋值为0，其余位置赋最小值。这些措施是为了保证只有当要加入物品体积之和与背包容积相等时才能入包。

验证：

• 当前位置是Integer.MIN_VALUE：dp2[j-v[i]] == dp2[0]，dp2[0]+w[i]>0，入数组。
• 加入所剩容积所指示位置不为Integer.MIN_VALUE：dp2[j-v[i]]>0，dp2[0]+w[i]>0，入数组。

整体代码示例：

import java.util.*;

public class Main {
    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int V = sc.nextInt();
        //物体体积
        int[] v = new int[n];
        //物体价值
        int[] w = new int[n];

        for (int i = 0; i < n; i++) {
            v[i] = sc.nextInt();
            w[i] = sc.nextInt();
        }

        //用体积数作为下标, 可以找到体积数对应的价值
        int[] dp1 = new int[V+1];
        int[] dp2 = new int[V+1];
        Arrays.fill(dp2, Integer.MIN_VALUE); //用来区分放了东西价值为零, 还是没放东西
        dp2[0] = 0;
        //物品遍历
        for (int i = 0; i < n; i++) {
            for (int j = V; j >= v[i]; j--){
                dp1[j] = Math.max(dp1[j], dp1[j-v[i]]+w[i]);
                dp2[j] = Math.max(dp2[j], dp2[j-v[i]]+w[i]);
            }
           
        }
        System.out.println(dp1[V]);
      //dp2[V] < 0表示不能满足正好放满的条件
        System.out.println(dp2[V] < 0 ? 0 : dp2[V]);
    }
}