题解 | #购物单#

const rl = require("readline").createInterface({
    input: process.stdin,
    output: process.stdout,
});
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void (async function () {
    // 读取 n 和 m 的值
    const line1 = await readline();
    let [n, m] = line1.split(" ").map(Number);

    // 初始化主件和附件价格和重要性数组，主件索引为0，附件索引为1和2，长度为3
    let price = new Array(m + 1).fill(0).map(() => new Array(3).fill(0));
    let importance = new Array(m + 1).fill(0).map(() => new Array(3).fill(0));

    // 读取物品的价值、价格和类型
    for (let i = 1; i <= m; i++) {
        const line = await readline();
        // v: 价格, p: 重要性, q: 类型
        let [v, p, q] = line.split(" ").map(Number);
        // 计算重要性
        let im = v * p;
        // 类型为 0 时，说明类型为主件，没有附件的情况
        if (q === 0) {
            price[i][0] = v;
            importance[i][0] = im;
        } else {
            // 类型不为 0 时，说明类型为附件
            if (price[q][1] === 0) {
                // 计算主件编号对应的第一个附件的价格和重要性
                price[q][1] = v;
                importance[q][1] = im;
            } else {
                // 计算主件编号对应的第二个附件的价格和重要性
                price[q][2] = v;
                importance[q][2] = im;
            }
        }
    }

    // 初始化动态规划数组，dp[i] 表示现在剩余可用金钱为 i 时的最大价值
    let dp = new Array(n + 1).fill(0);

    // 动态规划计算最大价值
    for (let i = 1; i <= m; i++) {
        if (price[i][0] === 0) continue;
        for (let j = n; j >= price[i][0]; j--) {
            // a: 当前主件价格, a1: 主件重要性
            let a = price[i][0];
            let a1 = importance[i][0];
            // b: 当前主件价格对应的附件价格, b1: 当前主件价格对应的附件重要性
            let b = price[i][1];
            let b1 = importance[i][1];
            // c: 当前主件价格对应的附件价格, c1: 当前主件价格对应的附件重要性
            let c = price[i][2];
            let c1 = importance[i][2];
            // 动态规划计算，计算当前金钱下的最大价值，比较主件，主件+附件1，主件+附件2，主件+附件1+附件2的情况
            // 如果当前金钱大于主件价格，取最大值
            if (j >= a) {
                dp[j] = Math.max(dp[j], dp[j - a] + a1);
            }
            // 如果当前金钱大于主件和附件1的价格，取最大值
            if (j >= a + b) {
                dp[j] = Math.max(dp[j], dp[j - a - b] + a1 + b1);
            }
            // 如果当前金钱大于主件和附件2的价格，取最大值
            if (j >= a + c) {
                dp[j] = Math.max(dp[j], dp[j - a - c] + a1 + c1);
            }
            // 如果当前金钱大于主件和附件1和附件2的价格，取最大值
            if (j >= a + b + c) {
                dp[j] = Math.max(dp[j], dp[j - a - b - c] + a1 + b1 + c1);
            }
        }
    }

    // 输出最大价值
    console.log(dp[n]);
})();