题解 | #购物单#

整合了题解里最高赞的两位大佬的题解，动态规划（空间压缩）的代码运行报错，经过排查出现两个问题：

1.new GOODS();爆红，输出静态方法不能引用非静态变量的异常；

2. if (goods[q-1].a1 == -1) { 最后一个示例报空指针异常——原因是没有全部初始化。比如第一个物品是第五个的附件，那么找不到第五个的a1的值。

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {

    private static class good {
        public int v;  //物品的价格
        public int p;  //物品的重要度
        public int q;  //物品的主附件ID

        public int a1 = -1; //附件1ID
        public int a2 = -1; //附件2ID

        public good(int v, int p, int q) {
            this.v = v;
            this.p = p;
            this.q = q;
        }

        public void setA1(int a1) {
            this.a1 = a1;
        }

        public void setA2(int a2) {
            this.a2 = a2;
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt(); //记录总共要买的物品数量
        int m = in.nextInt();

        good[] goods = new good[m];

        for (int i = 0; i < m; i++) {
            int v1 = in.nextInt();
            int p1 = in.nextInt();
            int q1 = in.nextInt();

            goods[i] = new good(v1, p1 * v1, q1); //直接计算好价值
        }

        for (int i = 0; i < m; i++) {

            if (goods[i].q > 0) {
                if (goods[goods[i].q-1].a1 == -1) {
                    goods[goods[i].q-1].a1 = i;
                } else {
                    goods[goods[i].q-1].a2 = i;
                }
            }
        }


        //转为01背包问题 倒序
        int[] dp = new int[N + 1];
        for (int i = 1; i <= m;
                i++) { //i指的是物品的次序，和goods[]的下标不一致
            for (int j = N; j >= 0; j--) {
                if (goods[i - 1].q > 0) {
                    continue;//这是附件，跳过
                }
                if (j >= goods[i - 1].v) {
                    //情况一：选/不选该物品
                    dp[j] = Math.max(dp[j], dp[j - goods[i - 1].v] + goods[i - 1].p);
                }
                if (goods[i - 1].a1 != -1 && j >= goods[i - 1].v + goods[goods[i - 1].a1].v) {
                    //情况二：选不选该物品的附件一
                    dp[j] = Math.max(dp[j], dp[j - goods[i - 1].v - goods[goods[i - 1].a1].v] +
                                     goods[i - 1].p + goods[goods[i - 1].a1].p);
                }
                if (goods[i - 1].a2 != -1 && j >= goods[i - 1].v + goods[goods[i - 1].a2].v) {
                    //情况三：选不选该物品的附件二
                    dp[j] = Math.max(dp[j], dp[j - goods[i - 1].v - goods[goods[i - 1].a2].v] +
                                     goods[i - 1].p + goods[goods[i - 1].a2].p);
                }
                if (goods[i - 1].a1 != -1 && goods[i - 1].a2 != -1 &&
                        j >= goods[i - 1].v + goods[goods[i - 1].a1].v + goods[goods[i - 1].a2].v) {
                    //情况四：选不选该物品的两个附件
                    dp[j] = Math.max(dp[j], dp[j - goods[i - 1].v - goods[goods[i - 1].a1].v -
                                               goods[goods[i - 1].a2].v] + goods[i - 1].p + goods[goods[i - 1].a1].p +
                                     goods[goods[i - 1].a2].p);

                }

            }
        }
        System.out.println(dp[N]);
    }

}