题解 | #购物单#

import java.util.*;

public class Main { public static void main(String[] args) { Scanner scan = new Scanner(System.in); int money = scan.nextInt(); int m = scan.nextInt(); if (money <= 0 || m <= 0) System.out.println(0);

    //给物品类赋值
    Good[] goods = new Good[m + 1];
    for (int i = 1; i < m + 1; i++) {
         goods[i] = new Good();
    }
    for (int i = 1; i < m + 1; i++) {
        int v = scan.nextInt();
        int p = scan.nextInt();
        int q = scan.nextInt();
        goods[i].setAll(v,p,q);

// System.out.println(goods[i].v+" "+goods[i].p+" "+goods[i].q);

        //判断是否为主件
        if (q > 0) { //附件
            if (goods[q].a1 == 0) {
                goods[q].setA1(i);
            } else {
                goods[q].setA2(i);
            }
        }
    }
    //开始动态规划
    int[][] dp = new int[m + 1][money + 1];
    //开始m循环
    for (int i = 1; i < m + 1; i++) {
        //每一个主件分四种情况
        int[] vs = new int[4];
        int[] dps = new int[4];
        int a1 = goods[i].a1;
        int a2 = goods[i].a2;
        //只有主件
        vs[0] = goods[i].v;
        dps[0] = goods[i].p * vs[0];
        //主件加附件1,需要先判断是否有附件
        if (a1 != 0) {
            vs[1] = goods[a1].v + vs[0];
            dps[1] = goods[a1].p * goods[a1].v + dps[0];
        }
        //主件加附件2
        if (a2 != 0) {
            vs[2] = goods[a2].v + vs[0];
            dps[2] = goods[a2].p * goods[a2].v + dps[0];
        }
        //主件加附件1,2
        if (a1 != 0 && a2 != 0) {
            vs[3] = vs[0] + goods[a1].v + goods[a2].v;
            dps[3] = dps[0] + goods[a1].p * goods[a1].v + goods[a2].p * goods[a2].v;
        }

        //开始money循环
        for (int j = 1; j <= money; j++) {
            if (goods[i].q > 0||
                    goods[i].v>j) { //物品重量过大或者物品为附件，则跳过;
                dp[i][j] = dp[i - 1][j];
            } else {
                //分四种情况，按顺序进行判断赋值,
                if (j >= vs[0]) dp[i][j] = Math.max(dp[i - 1][j],
                                                        dp[i - 1][j - vs[0]] + dps[0]);
                if (j >= vs[1]) dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - vs[1]] + dps[1]);
                if (j >= vs[2]) dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - vs[2]] + dps[2]);
                if (j >= vs[3]) dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - vs[3]] + dps[3]);

            }
        }

    }
    System.out.println(dp[m][money]);
}


//定义物品类
static class Good {
    public int v;
    public int p;
    public int q;

    public int a1 = 0; //附件的编号
    public int a2 = 0;
    
    public Good(){};
    public void setAll(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;
    }
}

}