题解 | #购物单#

import java.util.Scanner;

import java.util.*; 

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // // 注意 hasNext 和 hasNextLine 的区别
        // while (in.hasNextInt()) { // 注意 while 处理多个 case
        //     int a = in.nextInt();
        //     int b = in.nextInt();
        //     System.out.println(a + b);
        // }

        //1. 首先定义一个物品类 Good
        //2. 入参赋值
        int money = in.nextInt();  //总钱数
        int num   = in.nextInt();  //物品总件数
        //3. 入参校验
        if(money<=0 || num<=0){
            System.out.println(0);
        }

        //4. 填充物品数组 + 生成一个id对应的满意度数组，方便后序使用 + 记录物品最小的价格，后序可做剪枝 + 记录第一个主件的id
        Good[] goods = new Good[num+1];
        int[] sat = new int[num+1];
        int minVal = Integer.MAX_VALUE;  // 后面要取最小这里要赋值个最大值  
        int firstMainId = 0;
        //4.1 物品数组从1开始，因为附件的所属主件id也是从1开始
        for(int i=1; i<= num; i++){
            int v = in.nextInt();
            int p = in.nextInt();
            int q = in.nextInt();
            Good g = new Good(v,p,q);
            goods[i] = g;
            sat[i] = v*p;  //满意度=每件物品的价格*重要度乘积
            minVal = Math.min(minVal, v);
        }

        //4.2 如果q大于0，则需要为对应的主件打上附件标签。(分两个for执行因为有可能附件先来，此时主键还未创建)
        for(int i=1; i<=num; i++){
            int q = goods[i].q;
            if(q >0){
                if(goods[q].a1 ==-1){
                    goods[q].setA1(i);
                }else {
                    goods[q].setA2(i);
                }
            }else if(q==0 && firstMainId==0){
                //记录第一个主件
                firstMainId =i;
            }
        }
             

        //5. 解题思路： 动态规划dp[i][j]
        //5.1 i，j的代表意义，i个物品（注意是总i个，不是取了i个），j金钱可达到的最大满意度为dp[i][j]
        //5.2 递推公式：
        /** 共有5种情况
            1) 不购买当前物品： dp[i][j] = dp[i-1][j] 
            2) 购买当前物品，但不够买当前物品的附件： dp[i][j] = dp[i-1][j-goods[i].v] + sat[i];
            3) 购买当前物品，且购买附件1(如有)；dp[i][j] = dp[i-1][j-(goods[i].v)-(goods[goods[i].a1].v)] + sat[i] + sat[goods[i].a1] 
            4）购买当前物品，且购买附件2（如有）；dp[i][j] = dp[i-1][j-(goods[i].v)-(goods[goods[i].a2].v)] + sat[i] + sat[goods[i].a2]
            5）购买当前物品，且购买附件1,2（如有）,dp[i][j] = dp[i-1][j-(goods[i].v)-(goods[goods[i].a1].v)-(goods[goods[i].a2])] + sat[i] + sat[goods[i].a1] + sat[goods[i].a2]

            以上五种情况，第1）可以搭配后面四种情况，后面四种情况是根据物品情况才有， 所以dp[i][j]= max(1)情况，2)情况（如有），3)情况（如有），4情况（如有），5情况（如有）)
         */

         
         int[][] dp = new int[num+1][money+1];
         //注意此处i要从1开始，因为跟物品的id对应上， j可以从0开始
         for(int i =1; i<=num ; i++){
            for(int j=0; j<=money; j++){
                //6.1 【初始化dp数组】，j=0 无钱 dp[i][0]=0; 
                if(j==0){
                    dp[i][j] =0;
                    continue;
                }

                //6.2 【初始化dp数组】，当i<第一个主件id，dp[i][j]=0; 因为附件不可以单独购买
                if(i<firstMainId){
                    dp[i][j] =0;
                    continue;
                }

                //7.1 【剪枝】：如果j< 最便宜的价格，则也直接等于0
                if(j < minVal){
                    dp[i][j] =0;
                    continue;
                }

                //其他的均初始化dp[i][j]为情况1)
                dp[i][j] = dp[i-1][j];

                //7.2 【剪枝】：如果当前物品只是附件，直接等于不取附件的dp[i-1][j] continue
                if(goods[i].q >0){
                    //System.out.printf("i=%d, j=%d, dp[i][j]=%d%n", i, j, dp[i][j]);
                    continue;
                }

                if(j>=goods[i].v){   //情况2）
                    dp[i][j] = Math.max(dp[i][j], dp[i-1][j-goods[i].v] + sat[i]);
                }

                //条件不是互斥的，要继续用if，不是else-if
                //情况 3）
                int a1Id = goods[i].a1;
                if(a1Id !=-1 && j>= goods[i].v + goods[a1Id].v){
                    dp[i][j] = Math.max(dp[i][j], dp[i-1][j-goods[i].v-goods[a1Id].v] + sat[i] + sat[a1Id]);
                }

                int a2Id = goods[i].a2;
                if(a2Id !=-1 && j>= goods[i].v + goods[a2Id].v){
                    dp[i][j] = Math.max(dp[i][j], dp[i-1][j-goods[i].v-goods[a2Id].v] +sat[i] +sat[a2Id]);
                }

                if(a1Id !=-1 && a2Id !=-1 && j>=goods[i].v + goods[a1Id].v + goods[a2Id].v){
                    dp[i][j] = Math.max(dp[i][j], dp[i-1][j-goods[i].v-goods[a1Id].v-goods[a2Id].v] + sat[i] + sat[a1Id] + sat[a2Id]);
                }
            }
            
         }
         System.out.println(dp[num][money]);
    }

    public static class Good{
        public int v; //物品价格
        public int p; //物品重要度
        public int q; //0主件 >0为主键id

        public int a1 =-1; //附件1 id(需要给个初始值，后序赋值才能判断附件1是否有值了)
        public int a2 =-1; //附件2 id

        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;
        }
    }
}