题解 | 购物单

const readline = require("readline");

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});

let cnt = 0;

let totalBudget: number;
let totalItems: number;

let prices: number[][] = [];
let weights: number[][] = [];

rl.on("line", function (line: string) {
    const lineNum: number[] = line.split(" ").map(Number);

    if (cnt === 0) {
        // 初始化价格和重要度表
        [totalBudget, totalItems] = lineNum;
        totalBudget /= 10;

        prices = Array.from({ length: totalItems + 1 }, () => [0, 0, 0]);
        weights = Array.from({ length: totalItems + 1 }, () => [0, 0, 0]);
    } else {
        // 填充价格和重要度表数据
        const [itemPrice, itemWeight, itemParent] = lineNum;

        if (itemParent === 0) {
            // 当前物品为主件
            prices[cnt][0] = itemPrice / 10;
            weights[cnt][0] = itemWeight;
        } else {
            if (prices[itemParent][1] === 0) {
                // 当前物品是否为第一个附件
                prices[itemParent][1] = itemPrice / 10;
                weights[itemParent][1] = itemWeight;
            } else {
                prices[itemParent][2] = itemPrice / 10;
                weights[itemParent][2] = itemWeight;
            }
        }
    }

    cnt++;
});

rl.on("close", function () {
    // console.log(`prices`, prices)
    // console.log(`weights`, weights)

    const dp: number[][] = [];

    for (let i = 0; i <= totalItems; i++) {
        dp[i] = new Array(totalBudget + 1).fill(0);
    }

    // 初始化 dp 数组
    for (let i = 1; i <= totalItems; i++) {
        for (let j = 1; j <= totalBudget; j++) {
            const mainPrice = prices[i][0];
            const mainWeight = weights[i][0];

            const subPrice1 = prices[i][1];
            const subWeight1 = weights[i][1];

            const subPrice2 = prices[i][2];
            const subWeight2 = weights[i][2];

            // 是否加入当前主件
            dp[i][j] =
                j >= mainPrice
                    ? Math.max(
                          dp[i - 1][j - mainPrice] + mainPrice * mainWeight,
                          dp[i - 1][j]
                      )
                    : dp[i - 1][j];
            // 是否加入附件 1
            dp[i][j] =
                j >= mainPrice + subPrice1
                    ? Math.max(
                          dp[i - 1][j - mainPrice - subPrice1] +
                              mainPrice * mainWeight +
                              subPrice1 * subWeight1,
                          dp[i][j]
                      )
                    : dp[i][j];
            dp[i][j] =
                j >= mainPrice + subPrice2
                    ? Math.max(
                          dp[i - 1][j - mainPrice - subPrice2] +
                              mainPrice * mainWeight +
                              subPrice2 * subWeight2,
                          dp[i][j]
                      )
                    : dp[i][j];
            dp[i][j] =
                j >= mainPrice + subPrice1 + subPrice2
                    ? Math.max(
                          dp[i - 1][j - mainPrice - subPrice1 - subPrice2] +
                              mainPrice * mainWeight +
                              subPrice1 * subWeight1 +
                              subPrice2 * subWeight2,
                          dp[i][j]
                      )
                    : dp[i][j];
            // console.log(`dp[i][j]: ${i}, ${j}, ${dp[i][j]}`)
        }
    }
    console.log(dp[totalItems][totalBudget] * 10);
});