题解 | #购物单#01动态规划

import java.util.*;
public class Main {
        public static void main(String[] args) {
            Scanner in = new Scanner(System.in);
            int money = in.nextInt();
            int num = in.nextInt();
            money /= 10; //为了后边数组空间小一些
            int[][] price = new int[num + 1][3];// 标记 主件、附件1、附件2
            int[][] weight = new int[num + 1][3];
            //赋值循环
            for(int i = 1; i <= num; i++){
                int a = in.nextInt() / 10;//价格
                int b = in.nextInt() * a;//满意度
                int c = in.nextInt();//是否附件
                if(c == 0){//主件
                    price[i][0] = a ;
                    weight[i][0] = b ;
                }else if(price[c][1] == 0){//附件1
                    price[c][1] = a ;
                    weight[c][1] = b ;
                }else{//附件2
                    price[c][2] = a ;
                    weight[c][2] = b ;
                }
            }
            //声明状态转移矩阵
            int[][] dp = new int[num + 1][money + 1];
            //动态规划 递归计算
            for(int i = 1; i <= num; i++){//可以购买前i种货物
            //将第i种货物的价格、满意度取出来
            //价格
            int a = price[i][0];
            int b = price[i][1];
            int c = price[i][2];
            //满意度
            int d = weight[i][0];
            int e = weight[i][1];
            int f = weight[i][2];
                //按逻辑列举出所有转移的因果
                for(int j = 1; j<= money; j++){//钱包里有j钱
                    //购买分四种情况：只买主件、主+附1、主+附2、主+附件12，因此会有四个取舍
                    //可以买第i个货物，取“把钱花在前一个状态”和“买第i个货物”的最大值
                    //买不起就只加个钱，状态不变
                    dp[i][j] = j >= a ? Math.max(dp[i-1][j], dp[i-1][j-a]+d) : dp[i-1][j];
                    //上式已经更新了最优解，下面最大值的比较应替换为dp[i][j]
                    dp[i][j] = j >= a+b ? Math.max(dp[i][j], dp[i-1][j-a-b]+d+e) : dp[i][j];
                    dp[i][j] = j >= a+c ? Math.max(dp[i][j], dp[i-1][j-a-c]+d+f) : dp[i][j];
                    dp[i][j] = j >= a+b+c ? Math.max(dp[i][j], dp[i-1][j-a-b-c]+d+e+f) : dp[i][j];
                }
            }
             System.out.println(dp[num][money] * 10);
        }
}