题解 | #购物单#

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
    //1. 读取数据
    let token = [];
    while ((line = await readline())) {
        let tokens = line.split(" ");
        token.push(tokens.map(Number));
    }
    let [N, m] = token[0];
    let V = [0],
        W = [0],
        R = [0];
    let temp;
    for (let i = 1; i < token.length; i++) {
        V.push(token[i][0]);
        W.push(token[i][1]);
        R.push(token[i][2]);
    }

    //2. 分段
    //求最大公因数
    function gcd(a, b) {
        if (b == 0) {
            return a;
        }
        var r = a % b;
        return gcd(b, r);
    }
    //求一组数的最大公因数
    let gap = V.concat(N).reduce((prev, curr) => gcd(prev, curr));
    //统一单位大小
    V = V.map((v) => v / gap);
    //dp表
    let containerLength = N / gap;
    let container = new Array(containerLength + 1).fill(0);

    let inCart = new Array(containerLength + 1).fill(new Array(1).fill(0));
    for (let i = 1; i < m + 1; i++) {
        //前i个物体
        for (let j = containerLength; j >= V[i]; j--) {
            //容量为j
            let curr = j,
                before = j - V[i];
            let wealth,
                currValue,
                prevValue = container[curr];
            let [mainItemValue, mainItemWeight] = [V[R[i]], W[R[i]]];
            //       console.log(i,container);
            //       console.log(inCart[curr]);
            if (!inCart[before].includes(i)) {
                //没有重复当前的这个物件
                if (inCart[before].includes(R[i])) {
                    //如果主件已入购物车
                    wealth = V[i] * W[i];
                    currValue = container[j - V[i]] + wealth;
                    if (currValue > prevValue) {
                        container[j] = currValue;
                        inCart[curr] = inCart[before].concat([i]);
                    }
                } else if (j - mainItemValue - V[i] >= 0) {
                    //如果主件没进，那么考虑把主件也并在一起
                    wealth = mainItemValue * mainItemWeight + V[i] * W[i];
                    currValue = container[j - mainItemValue - V[i]] + wealth;
                    if (
                        !inCart[j - mainItemValue - V[i]].includes(i) &&
                        //                      !inCart[j-mainItemValue-V[i]].includes(R[i])  &&
                        currValue > prevValue
                    ) {
                        container[j] = currValue;
                        inCart[curr] = inCart[j - mainItemValue - V[i]].concat([
                            i,
                            R[i],
                        ]);
                    }
                }
            }
        }
    }
    console.log(container[containerLength] * gap);
})();

好难啊，一定要知道背包问题的解法