题解 | 购物单

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;
function maxSatisfaction(n, m, items) {
    // 分离主件和附件
    const main = [],
        attach = {};
    items.forEach(([v, w, q], i) => {
        if (q === 0) main.push({ v, w, id: i + 1 });
        else (attach[q] = attach[q] || []).push({ v, w });
    });

    // 初始化DP数组 价格为0-50
    const dp = new Array(n + 1).fill(0);

    // 处理每个主件及其可能的组合
    main.forEach((item) => {
        const { v, w } = item;
        const parts = attach[item.id] || [];

        // 生成所有可能的组合
        const combos = [
            { cost: v, value: v * w }, // 仅主件
            ...(parts[0]
                ? [
                      {
                          // 主件+附件1
                          cost: v + parts[0].v,
                          value: v * w + parts[0].v * parts[0].w,
                      },
                  ]
                : []),
            ...(parts[1]
                ? [
                      {
                          // 主件+附件2
                          cost: v + parts[1].v,
                          value: v * w + parts[1].v * parts[1].w,
                      },
                  ]
                : []),
            ...(parts[1]
                ? [
                      {
                          // 主件+两个附件
                          cost: v + parts[0].v + parts[1].v,
                          value:
                              v * w +
                              parts[0].v * parts[0].w +
                              parts[1].v * parts[1].w,
                      },
                  ]
                : []),
        ];

        // 更新DP数组
        // 重点：这里需要从大到小更新，因为每个主件只能选一次
        for (let j = n; j >= 0; j--) {
            for (const { cost, value } of combos) {
                if (j >= cost) {
                    const val = dp[j];
                    const val1 = dp[j - cost] + value;
                    dp[j] = Math.max(dp[j], dp[j - cost] + value);
                }
            }
        }
    });

    return dp[n];
}
void (async function () {
    // Write your code here
    const token = await readline();
    const totalPrice = parseInt(token.split(" ")[0]);
    const count = parseInt(token.split(" ")[1]);
    let inputs = [];
    let line = "";
    while ((line = await readline())) {
        inputs.push(line.split(" ").map((n) => parseInt(n)));
    }
    console.log(maxSatisfaction(totalPrice, count, inputs));
})();