题解 | 购物单

import java.util.Scanner;
import java.lang.Math;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNext()) { // 注意 while 处理多个 case
            int totalMoney = in.nextInt();
            int rowNum = in.nextInt();
            int[] price = new int[rowNum+1];
            int[] weight = new int[rowNum+1];
            int[] master = new int[rowNum+1];
            int[] attach1 = new int[rowNum+1];
            int[] attach2 = new int[rowNum+1];
            int[] maxSatis = new int[totalMoney+1];
            for(int i = 1;i <= rowNum;i++){
                price[i] = in.nextInt();
                weight[i] = in.nextInt();
                master[i] = in.nextInt();

                // 将附件一、附件二进行存储，下标为主键编号，值为附件编号
                if(master[i] > 0){
                    if(attach1[master[i]] == 0){
                        attach1[master[i]] = i;
                    }else{
                        attach2[master[i]] = i;
                    }
                }
            }

            //遍历每个主件购买、及附带购买附件时的满意度
            for(int i = 1;i <= rowNum;i++){
                int pricei = price[i];
                int weighti = weight[i];

                //仅用主件进行计算，附件会同步计算
                if(master[i] != 0) continue;

                //计算对同一主件，四种不同的购买方案,一维代表方案编号，二维代表方案对应的消费和满意度
                int[][] plan = new int[4][2];
                int nowPlanNum = 0;
                //方案一，仅购买主件
                plan[0][0] = pricei;
                plan[0][1] = pricei*weighti;
                //方案二，仅购买主件+附件1
                int a1 = attach1[i];
                if(a1 != 0){
                    plan[1][0] = pricei+price[a1];
                    plan[1][1] = plan[0][1] + price[a1]*weight[a1];
                    nowPlanNum++;
                }
                //方案三，仅购买主件+附件2
                int a2 = attach2[i];
                if(a2 != 0){
                    plan[2][0] = pricei+price[a2];
                    plan[2][1] = plan[0][1] + price[a2]*weight[a2];
                    nowPlanNum++;
                }
                //方案四，购买主件+附件1+附件2
                if(a1 != 0 && a2 != 0){
                    plan[3][0] = pricei+price[a1]+price[a2];
                    plan[3][1] = plan[0][1] + price[a1]*weight[a1]+ price[a2]*weight[a2];
                    nowPlanNum++;
                }

                //根据总的金额，写入上述方案对应的满意度
                for(int j = totalMoney;j>=0;j--){
                    // 每种方案都进行比较和写入
                    for(int k = 0;k<= nowPlanNum;k++){
                        // 提取对应的消费和满意度
                        int cost = plan[k][0];
                        int satis = plan[k][1];
                        // 如果当前金额能覆盖对应消费，证明方案有效，写入满意度
                        if(j >= cost){
                            // 此处取{金额对应已写入的满意度,(当前方案满意度+余额已写入的满意度)}中最大值
                            // 背包问题的状态方程
                            maxSatis[j] = Math.max(maxSatis[j], maxSatis[j-cost]+satis);
                        }
                    }
                }
            }
            System.out.println(maxSatis[totalMoney]);
        }
    }
}