购物单

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
    let inputs = []
    while(line = await readline()){
        inputs.push(line.split(' ').map(n=>parseInt(n)))
    }
    let n=0,m=0;
    let primary = {},annex = {}
    n = inputs[0][0]
    m = inputs[0][1]
    for(let i=1;i<m+1;i++){
        let x,y,z;
        [x,y,z] = inputs[i];
        if (z===0){
            // 主件
            primary[i]=[x,y]
        }else{
            // 附件
            if(annex[z]){
                // 已经有记录,添加附件,没有记录,新增附件列表
                annex[z].push([x,y])
            }else{
                annex[z] = [[x,y]]
            }
        }
    }

    m = Object.keys(primary).length; //数量转为主件数量
    dp = []
    for(let i=0;i<m+1;i++){
        let temp = []
        for(let j=0;j<n+1;j++){
            temp.push(0)
        }
        dp.push(temp)
    }

    let w = [[]], v= [[]]
    
    for(let key in primary){
        let w_temp=[], v_temp=[];
        w_temp.push(primary[key][0]); //主件价格
        v_temp.push(primary[key][0]*primary[key][1]) //满意度
        if (annex[key]){
            w_temp.push(w_temp[0]+annex[key][0][0])//主件+附件1
            v_temp.push(v_temp[0]+annex[key][0][0]*annex[key][0][1])
            if(annex[key].length===2){ 
            //2个附件
                w_temp.push(w_temp[0]+annex[key][1][0])//主件+附件2
                v_temp.push(v_temp[0]+annex[key][1][0]*annex[key][1][1])
                w_temp.push(w_temp[0]+annex[key][0][0]+annex[key][1][0])//主件+附件1+附件2
                v_temp.push(v_temp[0]+annex[key][0][0]*annex[key][0][1]+annex[key][1][0]*annex[key][1][1])
            }
        }
        w.push(w_temp);
        v.push(v_temp);
    }
    for (let i=1;i<m+1;i++){
        for(let j=10;j<n+1;j+=10){
            let max_i = dp[i-1][j]
            for(let k=0;k<w[i].length;k++){
                if(j-w[i][k]>=0){
                    max_i=Math.max(max_i,dp[i-1][j-w[i][k]]+v[i][k])
                }
            }
            dp[i][j]=max_i
        }
    }
    console.log(dp[m][n])
}()

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);
})();