题解 | #购物单#

var line = readline()
var m = +line.split(' ')[0] // 钱
var n = +line.split(' ')[1] // 数量
// 目标  重要度 和价格的乘积总和最大
let arr = []
let index = 0
while(line = readline()) {
  let s = line.split(' ')
  let w = +s[0] // 重量 = 价格
  let v = +s[1] * w // 价值 = 价格乘以重要程度
  let q = +s[2] // 是否为主件
  if(q === 0) {
    if(!arr[index]){
      arr[index] = {}
    }
    arr[index].w = w;
    arr[index].v = v;
    if(!arr[index].children) {
      arr[index].children = []
    }
  } else {
    // 附件
    if(!arr[q - 1]){
      arr[q - 1] = {children: [], w: 0, v: 0};
    }
    if(!arr[q - 1].children) {
      arr[q - 1].children = []
    }
    arr[q - 1].children.push({
      w,v
    })
  }
  index++;
}
// 处理array 变成0-1 背包的形式
let w = []
let v = []
arr.forEach(item => {
  let tempW = []
  let tempV = []
  tempW.push(item.w)
  tempV.push(item.v)
  let cw = 0; // 附件的总重
  let cv = 0; // 附件的总价值
  item.children.forEach(child => {
    tempW.push(child.w + item.w)
    tempV.push(child.v + item.v)
    cw += child.w;
    cv += child.v
  })
  if(cw > 0) {
    tempW.push(cw + item.w)
    tempV.push(cv + item.v)
  }
  w.push(tempW)
  v.push(tempV)
})
n = w.length;
let dp = [[]]
for (let i = 0; i <= m; i++) {
    dp[i] = new Array(n).fill(0);
    if (i >= w[0][0]) {
        dp[i][0] = w[0][0];
    }
}

for (let i = 0; i <= m; i++) { // i 是总重量
    for (let j = 0; j < n; j++) { // j 第j个物品
         let f = false; // 判断该组w 也就是w[i] 是否有 背包重量 大于 当前物品重量的情况， 如果有， 就不能 不放该组内的物品 也就是 原01背包内的else内的部分 
        for (let k = 0; k < w[j].length; k++) {
            if (i >= w[j][k]) { // 如果剩余重量 大于当前物品重量
                f = true;
                dp[i][j] = Math.max(dp[i][j - 1] || 0, (dp[i - w[j][k]][j - 1] || 0) + v[j][k], dp[i][j]); // 也要和自己取最大值
            } else if (!f) {
                dp[i][j] = dp[i][j - 1] || 0
            }
        }
    }
}
console.log(dp[m][n - 1])