题解 | #购物单#

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt() / 10;
        int m = in.nextInt();
        int[] prices = new int[m + 1];
        int[] values = new int[m + 1];
        int[] isLeaders = new int[m + 1];
        int[] f1s = new int[m + 1];
        int[] f2s = new int[m + 1];
        for (int i = 1; i <= m; i++) {
            prices[i] = in.nextInt() / 10;
            values[i] = prices[i] * 10 * in.nextInt();
            int leader = in.nextInt();
            if (leader == 0) {
                isLeaders[i] = 1;
            }
            else {
                if (f1s[leader] == 0) {
                    f1s[leader] = i; 
                }
                else {
                    f2s[leader] = i;
                }
            }
        }
        int[][] maxValue = new int[n + 1][m + 1]; // default = 0;
        for (int i = 1; i < n + 1; i++) {
            for (int j = 1; j < m + 1; j++) {
                if (isLeaders[j] == 0) {
                    maxValue[i][j] = maxValue[i][j-1];
                    continue;
                }
                int[] ops = new int[5];
                int f1 = f1s[j];
                int f2 = f2s[j];
                ops[0] = maxValue[i][j-1]; // 不买
                // 只买主件
                if (i - prices[j] >= 0) {
                    ops[1] = maxValue[i - prices[j]][j - 1] + values[j];
                }
                // 主件+附件1
                if (i - prices[j] - prices[f1] >= 0) {
                    ops[2] = maxValue[i - prices[j] - prices[f1]][j - 1] + values[j] + values[f1];
                }
                // 主件+附件2
                if (i - prices[j] - prices[f2] >= 0) {
                    ops[3] = maxValue[i - prices[j] - prices[f2]][j - 1] + values[j] + values[f2];
                }
                // 主件+附件1+附件2
                if (i - prices[j]- prices[f1] - prices[f2] >= 0) {
                    ops[3] = maxValue[i - prices[j]- prices[f1] - prices[f2]][j - 1] + values[j] + values[f1] + values[f2];
                }
                maxValue[i][j] = 0;
                for (int k = 0; k < 5; k++) {
                    if (ops[k] > maxValue[i][j]) maxValue[i][j] = ops[k];
                }
            } 
        } 
        System.out.println(maxValue[n][m]);
    }
}

动态规划

f[n][m]表示余额为n，可选物品前m个时最高满意度

f[n][m] = max(不买物品m，只买物品m，买物品m+附件1， 买物品m+附件2， 买物品m+附件1与附件2 );