题解 | #购物单#

购物单

http://www.nowcoder.com/practice/f9c6f980eeec43ef85be20755ddbeaf4

不放附件的话01背包只需要math.max(dp[i-1][...], ...)判断放或者不放。
放附件的话先做基础判断：主件是必须的，先用正常01背包math.max(dp[i-1][...], ...)得到放主件的dp[i][j]
然后在放了主件的dp[i][j]基础上去判断放附件的情况；

即01背包动态规划的上一个状态为dp[i-1]...，而放附件的上一个状态为放主件的最优解dp[i][j]；
放两件附件的上一个状态为放一个附件的最优解。此处理解清楚了比较对象，就能正确写出0,1,2个附件的判断过程

理解了比较的顺序其实具体代码就不用看了，感兴趣的可以跳到下面第二部分一维数组空间优化。


let base = 10 //题目中最小间隔10
let [sum, num] = readline().split(' ')
sum = sum / base
let list = {}
for (let i = 0; i < num; i++) {
  let [a, b, c] = readline().split(' ').map(Number);
  if(c){ //lines[2]如果上面没有Number转换的话输入的是字符串0，if('0')为true
    list[c] = list[c] || []
    list[c][1] = list[c][1] || []
    list[c][1].push(a / base, a / base * b)
  }else{
    list[i+1] = list[i+1] || []
    list[i+1][0] = [a / base, a / base * b]
  }
}
list = [...Object.values(list)]
buy(list)
function buy(m) {
  let len = m.length
  let dp = Array.from({length: len}, (e) => new Array(sum + 1).fill(0))
  dp[-1] = new Array(sum+1).fill(0) //加一行-1用于第一行初始化中的边界i-1的判断
  for (let i = 0; i < len; i++) {
    for (let j = 1; j <= sum; j++) {
      if(j < m[i][0][0]) {
        dp[i][j] = dp[i-1][j]
      } else {
          //一共只有0，1,2个配件3种情况，手写3种判断，w、v分别代表重量和价值
          let w1, w2, v1, v2
          m[i][1] && (w1 = m[i][1][0], v1 = m[i][1][1], w2 = m[i][1][2], v2 = m[i][1][3])
          dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-m[i][0][0]] + m[i][0][1]) 
          //+undefined为NaN，NaN做判断都是false
          j >= m[i][0][0] + w1 && (dp[i][j] = Math.max(dp[i][j], dp[i-1][j-m[i][0][0]- w1] + m[i][0][1] + v1))
          //此处w2也用dp[i][j](上面w1比较后的结果)作比较，即v1,v2也在此处做了比较了
          j >= m[i][0][0] + w2 && (dp[i][j] = Math.max(dp[i][j], dp[i-1][j-m[i][0][0]- w2] + m[i][0][1] + v2))   
          j >= m[i][0][0] + w1 + w2 && (dp[i][j] = Math.max(dp[i][j], dp[i-1][j-m[i][0][0]- w1 - w2] + m[i][0][1] + v1 + v2)) 
      }
    }
  }
  print(dp[len-1][sum]*base)
}

一维数组空间优化，效果比滚动数组空间优化还要好，减少大量内存占用。
二维数组是dp[i - 1][j]跟dp[i - 1][j - w] + v 比较，滚动数组只用保存这两行数组交替往下迭代。
二维数组dp[i - 1][j]跟dp[i - 1][j - w] + v比较可以实现同一物体只放一次的效果（因为 i - 1 行每条数据都是没放w的状态，并且赋值dp[i][j]并没有修改dp[i - 1][...]的值），所以每次赋值dp[i][j]的结果都是上一行dp[i - 1][...]没有放w的值加上放入w的结果。
而如果用一维数组去比较dp[i - w]和dp[i - w] + v的话会因为修改了dp[i - w]的值，形成累加效果。
例如w = 2,v = 4, dp[0] - dp[10] 均为0
dp[0] = 0，dp[1] = 0，dp[2] = dp[0] + 4, dp[4] = dp[2] + 4。dp[4] = 0 + 4 + 4
但是如果一维数组改为逆序迭代就不会出现这个问题，不会造成累加且从物品w1开始迭代到物品wn, 上一次迭代结果也是保存在dp里了的。

let base = 10 //题目中最小间隔10
let [sum, num] = readline().split(' ')
sum = sum / base
let list = {}
for (let i = 0; i < num; i++) {
  let [a, b, c] = readline().split(' ').map(Number);
  if(c){ //lines[2]如果上面没有Number转换的话输入的是字符串0，if('0')为true
    list[c] = list[c] || []
    list[c][1] = list[c][1] || []
    list[c][1].push(a / base, a / base * b)
  }else{
    list[i+1] = list[i+1] || []
    list[i+1][0] = [a / base, a / base * b]
  }
}
list = [...Object.values(list)]
buy(list)
function buy(m) {
  let len = m.length
  let dp = Array.from({length: sum +1}, () => 0)
  for (let i = 0; i < len; i++) {
    for (let j = sum; j; j--) {    //逆序迭代
      if(j >= m[i][0][0]) {
          let w1, w2, v1, v2
          m[i][1] && (w1 = m[i][1][0], v1 = m[i][1][1], w2 = m[i][1][2], v2 = m[i][1][3])
          dp[j] = Math.max(dp[j],dp[j-m[i][0][0]] + m[i][0][1])
          j >= m[i][0][0] + w1 && (dp[j] = Math.max(dp[j], dp[j-m[i][0][0]- w1] + m[i][0][1] + v1))
          j >= m[i][0][0] + w2 && (dp[j] = Math.max(dp[j], dp[j-m[i][0][0]- w2] + m[i][0][1] + v2)) 
          j >= m[i][0][0] + w1 + w2 && (dp[j] = Math.max(dp[j], dp[j-m[i][0][0]- w1 - w2] + m[i][0][1] + v1 + v2))
      }
    }
  }
  print(dp[sum]*base)
}

然而提交代码可以看到占用空间排名还是很低，去看了别人代码，可以把0,1,2三种情况构造成需要遍历的数组对象，只写一个判断语句。假设输入：

构造主附件各种组合方式的重量和价值数组如下：

w:
[[800, 800+400, 800+300, 800+400+300],
 [400],
 [500]]
v:
[[1600,1600+2000,1600+1500,1600+2000+1500],
 [1200],
 [1000]]

//循环遍历每层的主附件组合即可
for(let s= 0; s < w.length; s++) {
  if (j - w[s] >= 0) {
    dp[j] = Math.max(dp[j], dp[j- w[s]] + v[s]);
  }
}

完整代码：

let base = 10 //题目中最小间隔10
var [sum, num] = readline().split(' ')
sum = sum / base
var list = {}
for (let i = 1; i <= num; i++) {
  var [a, b, c] = readline().split(' ').map(Number);
  if(c){
    list[c] = list[c] || []
    list[c].push([a / base, a / base * b])
  }else{
    list[i] = list[i] || []
    list[i].unshift([a / base, a / base * b])
  }
}
  let dp = Array.from({length: sum +1}, () => 0)
  //let arr = Array.from({length: sum+1}, (val, idx) => idx).reverse();
  Object.values(list).forEach(e => {
    let w = [],v = []    //构建主附件组合方式
    const [m, ...s] = e
    w.push(m[0])
    v.push(m[1])
    if(s[0]) {
    const [s1, s2] = s
        w.push(s1[0]+m[0])
        v.push(s1[1]+m[1])
        if(s2) {
            w.push(s2[0]+m[0])
            v.push(s2[1]+m[1])
            w.push(s1[0]+s2[0]+m[0])
            v.push(s1[1]+s2[1]+m[1])
        }
    }
     for (let j = sum; j; j--) {    //逆序迭代
            for(let s= 0; s < w.length; s++) {
              if (j - w[s] >= 0) {
                dp[j] = Math.max(dp[j], dp[j- w[s]] + v[s]);
              }
            }
      }
  })
  print(dp[sum]*base)

这里还有一个让我很费解的事情是，此处用forEach内存占用还会比for循环少1000kb。

//先构建一个需要遍历的总价值数组
let arr = Array.from({length: sum+1}, (val, idx) => idx).reverse();
//对上面的测试用例输入总价值1000来说，这个数组就是[100, 99, 98, 97, ..., 3, 2, 1, 0]
//由于这里已经是个reverse从大到小的顺序了，forEach遍历相当于是逆序迭代过程
//然后循环改写为
  arr.forEach(j => {    //逆序迭代
          for(let s= 0; s < w.length; s++) {
            if (j - w[s] >= 0) {
              dp[j] = Math.max(dp[j], dp[j- w[s]] + v[s]);
            }
          }
    })
//这里forEach为什么比for循环内存占用小呢，循环次数都是sum+1次。
//而且forEach根本无法停止，
//而由于输入的测试用例最小sum为50,这里for循环甚至可以写成for (let j = sum; j>4 ; j--) { ... } 也还是多1000内存