题解 | 购物单

import java.util.Scanner;

public class Main {

    static class Item {
        int v; // 价格
        int w; // 重要度
    }

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); // 预算
        int m = sc.nextInt(); // 物品数量

        //主件信息
        Item[] main = new Item[m + 1];

        //附件信息
        Item[][] attach = new Item[m + 1][2];

        //主件的附件数量
        int[] attachCount = new int[m + 1];

        //初始化
        for (int i = 1; i <= m; i++) {

            int v = sc.nextInt();
            int w = sc.nextInt();
            int q = sc.nextInt();

            if (q == 0) {
                main[i] = new Item();
                main[i].v = v;
                main[i].w = w;
            } else {
                attach[q][attachCount[q]] = new Item();
                attach[q][attachCount[q]].v = v;
                attach[q][attachCount[q]].w = w;
                attachCount[q]++;
            }
        }

        //dp【i】是花费i的最大满意度
        int[] dp = new int[n + 1];

        for (int i = 1; i <= m; i++) {

            if (main[i] == null) continue;

            int v0 = main[i].v;
            int w0 = v0 * main[i].w;

            int v1 = 0, w1 = 0;
            int v2 = 0, w2 = 0;

            if (attachCount[i] >= 1) {
                v1 = attach[i][0].v;
                w1 = v1 * attach[i][0].w;
            }

            if (attachCount[i] >= 2) {
                v2 = attach[i][1].v;
                w2 = v2 * attach[i][1].w;
            }

            //从后往前遍历背包容量，只允许购买一次
            for (int j = n; j >= v0; j--) {

                //只购买主件
                dp[j] = Math.max(dp[j], dp[j - v0] + w0);

                //只购买主件和第一件附件
                if (j >= v0 + v1)
                    dp[j] = Math.max(dp[j], dp[j - v0 - v1] + w0 + w1);
				//购买主件和第二件附件
                if (j >= v0 + v2)
                    dp[j] = Math.max(dp[j], dp[j - v0 - v2] + w0 + w2);
				//购买主件和两件附件
                if (j >= v0 + v1 + v2)
                    dp[j] = Math.max(dp[j], dp[j - v0 - v1 - v2] + w0 + w1 + w2);
            }
        }

        System.out.println(dp[n]);
    }
}