题解 | #购物单#

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int money = scanner.nextInt();
        int num = scanner.nextInt();
        int[][] prices = new int[num + 1][3];// 价格数组
        int[][] weights = new int[num + 1][3];// 价格与重要度乘积数组
        for (int i = 1; i <= num; i++) {
            int price = scanner.nextInt();
            int weight = scanner.nextInt();
            int index = scanner.nextInt();
            weight *= price;
            if (index == 0) {// 主件
                prices[i][0] = price;
                weights[i][0] = weight;
            } else if (prices[index][1] == 0) {// 附件1
                prices[index][1] = price;
                weights[index][1] = weight;
            } else {// 附件2
                prices[index][2] = price;
                weights[index][2] = weight;
            }
        }
        int[] dp = new int[money + 1];// dp数组
        for (int i = 1; i <= num; i++) {// 遍历物品
            for (int j = money; j >= 0; j -= 10) {// 遍历money
                int a = j - prices[i][0];
                int b = j - prices[i][0] - prices[i][1];
                int c = j - prices[i][0] - prices[i][2];
                int d = j - prices[i][0] - prices[i][1] - prices[i][2];
                int e = weights[i][0];
                int f = weights[i][0] + weights[i][1];
                int g = weights[i][0] + weights[i][2];
                int h =  weights[i][0] + weights[i][1] + weights[i][2];
                dp[j] = a >= 0 ? Math.max(dp[j], dp[a] + e) : dp[j];// 是否购买主件
                dp[j] = b >= 0 ? Math.max(dp[j], dp[b] + f) : dp[j];// 是否购买主件和附件1
                dp[j] = c >= 0 ? Math.max(dp[j], dp[c] + g) : dp[j];// 是否购买主件和附件2
                dp[j] = d >= 0 ? Math.max(dp[j], dp[d] + h) : dp[j];// 是否购买主件和附件1和附件2
            }
        }
        System.out.println(dp[money]);// 输出结果
    }
}