题解 | #购物单#

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static class good{ //定义商品类
        public int v;
        public int p;
        public int q; //对应题目

        //定义配件
        public int a1 = 0;
        public int a2 = 0;

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

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

    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int money = in.nextInt();
        int goodsNum = in.nextInt();
        //输入总价钱和商品个数
        if(goodsNum<=0 || money<=0){
            System.out.println(0);
        }

        //输入并初始化所有商品
        good[] goods = new good[goodsNum+1];//从1开始计数
        for(int i=1 ; i<=goodsNum ; ++i){
            int v = in.nextInt();
            int p = in.nextInt();
            int q = in.nextInt();
            goods[i] = new good(v,p,q);
        }

        //增加配件
        for(int i=1 ; i<=goodsNum ; ++i){
            int q = goods[i].q;
            if(q > 0){
                if(goods[q].a1 == 0){
                    goods[q].setA1(i);
                }
                else{
                    goods[q].setA2(i);
                }
            }
        }

        int[][] dp = new int[goodsNum+1][money+1];//设置了边界
        //思路，01背包问题
        for(int i=1 ; i<=goodsNum ; ++i){
            //四种情况
            int v=goods[i].v ,v1=0,v2=0,v3=0;
            int s=v * goods[i].p, s1=0, s2=0, s3=0; //表示满意程度
            if(goods[i].a1 != 0){
                v1 = v+goods[goods[i].a1].v;
                s1 = s + goods[goods[i].a1].v * goods[goods[i].a1].p;
            }
            if(goods[i].a2 != 0){
                v2 = v + goods[goods[i].a2].v;
                s2 = s + goods[goods[i].a2].v * goods[goods[i].a2].p;
            }
            if(goods[i].a1 !=0 && goods[i].a2 != 0){
                v3 = v1+v2-v;
                s3 =  s1+s2-s;
            }
            //二重循环
            for(int j=1 ; j<=money ; ++j){
                if(goods[i].q > 0){ //配件先跳过，从主键中选择配件
                    dp[i][j] = dp[i-1][j]; //花费j的钱够买前i件商品的部分
                }
                else{
                    dp[i][j] = dp[i-1][j]; //先回退到上一个状态
                    if(v != 0 && j>=v){
                        dp[i][j] = Math.max(dp[i][j], dp[i-1][j-v]+s);
                        //如果能装下，则比较装该物品或者不装该物品（一共要装i个物品，如果装这个就i-1少装一个状态再装）哪个满意度更高
                    }
                    if(v1!=0 && j>=v1){ //是否加第一个配件
                        dp[i][j] = Math.max(dp[i][j], dp[i-1][j-v1]+s1);
                    }
                    if(v2!=0 && j>=v2){
                        dp[i][j] = Math.max(dp[i][j], dp[i-1][j-v2]+s2);
                    }
                    if(v3!=0 && j>=v3){
                        dp[i][j] = Math.max(dp[i][j], dp[i-1][j-v3]+s3);
                    }
                }
            }
        }
        System.out.print(dp[goodsNum][money]);

    }
}