01背包问题

Code

/**
 * 商品名称 重量 价值
 * 物品1 2 5
 * 物品2 5 10
 * 物品3 1 3
 * 物品4 4 6
 * 物品5 3 3
 *
 * 背包最大6，请问题最多可以装多少价值东西
 */

分析

/**
 * 
 * 假设只有1个物品
 * 背包中6，的二维数组
 * [0, 0, 5, 5, 5, 5]
 * [0, 0, 5, 5, 10, 10]
 * [0, 3, 5, 8]
 * 
 * item => Math.max(value[i] + dp[i - 1][j - weight[i]],dp[i - 1][j])
 */

function packages(bagWeight, value, weight) {
  let line = [];
  // 搞定第一行
  for (let i = 0; i < bagWeight; i ++) {
    line[i] = i >= weight[0] ? value[0] : 0;
  }
  // 搞定剩余行
  for (let i = 1; i < value.length; i ++) {
    const next = [];
    for (let j = 0; j < bagWeight; j ++) {
      if (j < weight[i]) {
        next[j] = line[j];
      } else {
        next[j] = Math.max(value[i] + line[j - weight[i]],line[j])
      }
    }
    line = next
  }

  return line[bagWeight]
}