题解 | #购物单#

import java.util.Scanner;
import java.util.LinkedList;
import java.util.Comparator;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner s=new Scanner(System.in);
        int money=s.nextInt();
        int num=s.nextInt();
        
        Goods[] goods=new Goods[num];
        //初始化商品
        for(int i=0;i<num;i++){
            goods[i]=new Goods();
        }
        //将商品信息进行初始化
        for(int i=0;i<num;i++){
            int v=s.nextInt();
            int p=s.nextInt();
            int q=s.nextInt();
            goods[i].v=v;
            //直接计算价值
            goods[i].p=p*v;
            //如果该商品是主物品，设置为true
            if(q==0){
                goods[i].main=true;
                //判断商品的是否有附件，有附件，没有附件，就把该商品对应的主商品的附件设置为它
            }else if(goods[q-1].a1==-1){
                goods[q-1].a1=i;
            }else{
                goods[q-1].a2=i;
            }
        }
        //核心处理代码 动态规划问题，使用背包问题思想解决 （菜鸡一枚，可以优化时间复杂度的，双层循环太耗费时间了，可以根据i-1得出i的本次最优解）
        int[][] dp=new int[num+1][money+1];
        for(int i=1;i<=num;i++){
            for(int j=0;j<=money;j++){
			  //每次行遍历的时候，把满意度默认设置为不购买当前物品的满意度，也就是上一行的数据。
                dp[i][j]=dp[i-1][j];
                //不是主物品就不购买了
                if(!goods[i-1].main){
                    continue;
                }
                //主键+null   i-1表示当前用品，点v表示当前物品的价格
                if(j>=goods[i-1].v){
				  //从购买本商品和不购买本商品找出最大的满意度，dp[i-1]就是购买本商品的时候的满意度，加上剩余钱在当前物品下购买的时候的最大满意度。
				  //背包问题01中无非就是购买该商品或者不购买该商品，购买该商品就是当前的商品的满意度+剩下钱的满意度计算，不购买该商品就是从上一个商品价格表中的最优解
                  dp[i][j]=Math.max(dp[i][j],dp[i-1][j-goods[i-1].v]+goods[i-1].p);
                }
                //主键+附件1
                if(goods[i-1].a1!=-1&&j>=goods[i-1].v+goods[goods[i-1].a1].v){
                  dp[i][j]=Math.max(dp[i][j],dp[i-1][j-goods[i-1].v-goods[goods[i-1].a1].v]+goods[i-1].p+goods[goods[i-1].a1].p);
                }
                //主键+附件2
                if(goods[i-1].a2!=-1&&j>=goods[i-1].v+goods[goods[i-1].a2].v){
                    dp[i][j]=Math.max(dp[i][j],dp[i-1][j-goods[i-1].v-goods[goods[i-1].a2].v]+goods[i-1].p+goods[goods[i-1].a2].p);
                }
                //主键+附件1+附件2
                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[i][j]=Math.max(dp[i][j],dp[i-1][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[num][money]);
    }
}
class Goods{
    int v;
    //商品满意度=单价*重要度
    int p;
    boolean main=false;
    int a1=-1;
    int a2=-1;
}