题解 | 购物单 0-1背包问题+分类讨论

import java.util.*;

class Good {
    int v; // 价格
    int w; // 重要度
    int q; // 主件ID 或者 附件对应的主件ID

    // 每个主件最多有2个附件
    int addition1; // 附件1
    int addition2; // 附件2

    public Good(int v, int w, int q) {
        this.v = v;
        this.w = w;
        this.q = q;
    }

    public void setAddtion1(int addition1) {
        this.addition1 = addition1;
    }

    public void setAddtion2(int addition2) {
        this.addition2 = addition2;
    }
}

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            // 容量为n的背包，有m个物品可选
            int n = in.nextInt(), m = in.nextInt();
            int[] v = new int[n + 1];
            int[] w = new int[n + 1];
            int[] q = new int[n + 1];
            Good[] goods = new Good[n + 1];
            for (int i = 1; i <= m; i++) {
                v[i] = in.nextInt();
                w[i] = in.nextInt();
                q[i] = in.nextInt();
                goods[i] = new Good(v[i], w[i], q[i]);
            }

            // 处理附件的归属情况
            for (int i = 1; i <= m; i++) {
                int cur = goods[i].q;
                if (cur > 0) { // cur就是主件的下标
                    if (goods[cur].addition1 > 0) { // 已经存在一个附件
                        goods[cur].setAddtion2(i);
                    } else {
                        goods[cur].setAddtion1(i);
                    }
                }
            }

            // 容量为n的背包，有m个物品可选
            // 转换成0-1背包问题：
            // 1.不选主件 2.只选主件 3.选主件和附件1 4.选主件和附件2 5.选主件、附件1和附件2
            int[][] dp = new int[m + 1][n + 1];
            for (int i = 1; i <= m; i++) {
                // 当前物品的价格和满意度(只有主件)
                int v0 = v[i], sat0 = v[i] * w[i];
                int v1 = 0, sat1 = 0;
                int v2 = 0, sat2 = 0;
                int v3 = 0, sat3 = 0;

                // 主件+附件1
                int add1 = goods[i].addition1;
                if (add1 != 0) {
                    v1 = v[add1] + v0;
                    sat1 = v[add1] * w[add1] + sat0;
                }

                // 主件+附件2
                int add2 = goods[i].addition2;
                if (add2 != 0) {
                    v2 = v[add2] + v0;
                    sat2 = v[add2] * w[add2] + sat0;
                }

                // 主件+附件1+附件2
                if (add1 != 0 && add2 != 0) {
                    v3 = v[add1] + v[add2] + v0;
                    sat3 = v[add1] * w[add1] + v[add2] * w[add2] + sat0;
                }

                // 从前i个物品中选，当前容量为j
                for (int j = 1; j <= n; j++) {
                    if (goods[i].q > 0) { // 当物品i是附件时，跳过不选
                        dp[i][j] = dp[i - 1][j];
                    } else {
                        dp[i][j] = dp[i - 1][j];
                        // v != 0这个条件是用来判断是否有附件的，是否能进行操作，如果没附件，v就是最开始初始化的0
                        if (j >= v0 && v0 != 0) {
                            dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - v0] + sat0);
                        }
                        if (j >= v1 && v1 != 0) {
                            dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - v1] + sat1);
                        }
                        if (j >= v2 && v2 != 0) {
                            dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - v2] + sat2);
                        }
                        if (j >= v3 && v3 != 0) {
                            dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - v3] + sat3);
                        }
                    }
                }
            }
            System.out.println(dp[m][n]);
        }
    }
}