题解 | #购物单#

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

void (async function () {
    // Write your code here
    const primary = {};
    const annex = {};
    const f = new Array(32000).fill(0);
    line = await readline();
    let tokens = line.split(" ");
    let N = parseInt(tokens[0]); // 总钱数
    let m = parseInt(tokens[1]); // 总物品数
    for (let i = 1; i <= m; ++i) {
        let temp = await readline();
        let arr = temp.split(" ").map((ele) => parseInt(ele));
        if (arr[2] == 0) primary[i] = [arr[0], arr[1]];
        else {
            // 第二个附件
            if (Object.keys(annex).includes(arr[2].toString())) {//Object对象的键会自动转换为字符串类型
                annex[arr[2]][1] = [arr[0], arr[1]];
            } else {
                // 第一个附件
                //初始化一个二维数组
                annex[arr[2]] = new Array(2).fill(0).map(() => new Array(2).fill(0));
                annex[arr[2]][0] = [arr[0], arr[1]];
            }
        }
    }

    for (let key in primary) {
        //v_temp：价格，sa_temp：满意度
        const v_temp = [],
            sa_temp = [];
        // 1. 只有一个 主件
        v_temp.push(primary[key][0]);
        sa_temp.push(primary[key][0] * primary[key][1]);
        // 存在附件
        if (key in annex) {
            // 2. 主件 + 附件1
            v_temp.push(v_temp[0] + annex[key][0][0]);
            sa_temp.push(sa_temp[0] + annex[key][0][0] * annex[key][0][1]);
            // console.log(`annex[${key}]:${annex[key]}`);
            if (annex[key].length > 1) {
                //存在两个附件
                // 2. 主件 + 附件2
                v_temp.push(v_temp[0] + annex[key][1][0]);
                sa_temp.push(sa_temp[0] + annex[key][1][0] * annex[key][1][1]);
                // 3. 主件 + 附件1 + 附件2
                v_temp.push(v_temp[0] + annex[key][0][0] + annex[key][1][0]);
                sa_temp.push(
                    sa_temp[0] +
                        annex[key][0][0] * annex[key][0][1] +
                        annex[key][1][0] * annex[key][1][1]
                );
            }
        }
        // console.log('v_temp:',v_temp);
        // console.log('sa_temp:',sa_temp);

        for (let j = N; j >= 0; j -= 10) {
            for (let k in v_temp) {
                if (j - v_temp[k] >= 0) {
                    f[j] = Math.max(f[j], f[j - v_temp[k]] + sa_temp[k]);
                }
            }
        }
    }
    console.log(f[N]);
})();