题解 | #购物单#

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;
let sum = 0;
let num = 0;
let i = 0;
const goods = [];
const base = 10;
void (async function () {
    // Write your code here
    while ((line = await readline())) {
        if (!num) {
            [sum, num] = line.split(" ").map(Number);
            sum = sum / base;
        } else {
            if (i < num) {
                // console.log( i, num);
                makeArr(line, i);
                i++;
            } 
            if (i === num) {
                // console.log(goods,  i, num);
                fun(goods, sum);
            }
        }
    }
})();

const makeArr = (line, i) => {
    let [w, v, q] = line.split(" ").map(Number);
    w = w / base;
    v = v * w;
    if (q) {
        // 附件
        // goods[q - 1] = goods[q - 1] || [];
        if (!goods[q - 1]) {
            goods[q - 1] = { children: [], v: 0, w: 0 };
        }
        if (!goods[q - 1].children) {
            goods[q - 1].children = [];
        }
        goods[q - 1].children.push({ w, v });
    } else {
        // 主件
        if (!goods[i]) {
            goods[i] = {};
        }
        goods[i].v = v;
        goods[i].w = w;
        if (!goods[i].children) {
            goods[i].children = [];
        }
    }
};

const transArr = (arr) => {
    let wArr = [];
    let vArr = [];
    arr.forEach((item) => {
        // console.log(item);
        let tW = [];
        let tV = [];
        let cw = 0;
        let cv = 0;
        tW.push(item.w);
        tV.push(item.v);
        item.children.forEach((it) => {
            tW.push(it.w + item.w);
            tV.push(it.v + item.v);
            cw += it.w;
            cv += it.v;
        });
        if (cw > 0) {
            tW.push(cw + item.w);
            tV.push(cv + item.v);
        }
        wArr.push(tW);
        vArr.push(tV);
    });
    return { w: wArr, v: vArr };
};

const fun = (arr, total) => {
    const { w, v } = transArr(arr);
    // console.log("w:", w);
    // console.log("v:", v);
    let len = w.length;
    // const dp1 = new Array(total + 1).fill(0);
    // for (let i = 0; i < len; i++) {
    //     for (let j = total; j >= 0; j--) {
    //         let max = dp1[j];
    //         for (let k = 0; k < w[i].length; k++) {
    //             if (j >= w[i][k]) {
    //                 max = Math.max(max, dp1[j - w[i][k]] + v[i][k]);
    //             }
    //         }
    //         dp1[j] = max;
    //     }
    // }
    // console.log(dp1[total] * base);
    // return;
    const dp = [[]];

    for (let i = 0; i <= len; i++) {
        dp[i] = new Array(total + 1).fill(0);
    }
    for (let i = 0; i< len; i++ ) {
        for( let j = 0; j <= total; j++) {
            let max = dp[i][j];
            for (let k = 0; k< w[i].length; k++) {
                let wi = w[i][k];
                if (j >= wi ) {
                    max = Math.max(max, dp[i][j - wi] + v[i][k])
                } 
            }
            dp[i+1][j]= max;
        }
    }
    console.log(dp[len][total] * base);
};