题解 | #购物单#

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    while (sc.hasNextLine()) {
        //一、读取输入数据
        //读取第一行
        int money = sc.nextInt();//总钱数
        int m = sc.nextInt();//物品个数
        sc.nextLine();
        //小技巧，节省空间，因为写了money是10的倍数
        money /= 10;
        int[][] prices = new int[m+1][3];//价格表
        int[][] satisfied = new int[m+1][3];//满意度表
        for (int i = 1; i <= m; i++) {
            // sc.nextLine();放这里会数组越界错误
            int v = sc.nextInt();//价格
            int p = sc.nextInt();//重要度
            int q = sc.nextInt();//q=0主件，q代表所属主件编号
            v /= 10;
            if (q == 0) {// 这个是主件
                prices[i][0] = v;
                satisfied[i][0] = p*v;
            } else{ //这个是附件
                if (prices[q][1] == 0) {//该主件还没有添加过附件
                    prices[q][1] = v;
                    satisfied[q][1] = p*v;
                } else {
                    prices[q][2] = v;//该主件添加过附件，因为附件总共就2个，直接放到第2个去
                    satisfied[q][2] = p*v;
                }
            }   
            sc.nextLine();//sc指针转向下一行
        }
        
        //二、动态规划
        int[][] dp = new int[m+1][money+1];
        for (int i = 1; i <= m; i++) {
            for(int j = 1; j <= money; j++) {
                //只有主件的情况
                int a = prices[i][0];//没有附件的价格
                int b = satisfied[i][0];//没有附件的满意度
                dp[i][j] = j >= a ? Math.max(dp[i-1][j], dp[i-1][j-a] + b) : dp[i-1][j];
                //等效于上面那句话
                // if(j>a){
                //     dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-a] + b);
                // }else{
                //     dp[i][j] = dp[i-1][j];
                // }
                //有附件的情况，看看这个主件有没有附件，有附件要一起处理
                int c = prices[i][1];//第1个附件
                int d = satisfied[i][1];
                int e = prices[i][2];//第2个附件的价格
                int f = satisfied[i][2];
                //主件和第1个附件买得起，这里为什么还是i？自己要想想
                //这里其实应该加判断，看看有没有 第1附件 第2附件
                dp[i][j] = j>= a+c ? Math.max(dp[i][j], dp[i-1][j-a-c] + b + d):dp[i][j];
                //主件和第2个附件买得起
                dp[i][j] = j>= a+e ? Math.max(dp[i][j], dp[i-1][j-a-e] + b + f):dp[i][j];
                //主件和第1、第2个附件都买得起
                dp[i][j] = j>= a+c+e ? Math.max(dp[i][j], dp[i-1][j-a-c-e] + b +d + f):dp[i][j];
            }
        }
        System.out.println(dp[m][money] * 10);
    }

    }
}