01背包

给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。

const tList = [1, 2, 3, 4, 5]  // 物品体积const vList = [3, 4, 10, 7, 4] // 物品价值const map = {}function getbag (i, v) {  if (i === 0) {    if (tList[0] > v) {      return 0    } else {      return vList[0]    }  }  if (v >= tList[i]) {    // 放与不放 取最大值    return Math.max(getbag(i - 1, v), vList[i] + getbag(i - 1, v - tList[i]))      } else {    return getbag(i - 1, v)  }}console.log(getbag(5, 3))

完全背包

• 商品不限重复次数
• 状态转移方程从01背包的f[i][j] = max(f[i-1][j], f[i-1][j-w[i] + v[i])变成f[i][j] = max(f[i-1][j], f[i-1][j-k*w[i]]+k*v[i])且0<k<j/w[i]

const bag = 61const goodList = [{  name: 'apple',  w: 2,  v: 2}, {  name: 'book',  w: 3,  v: 7}, {  name: 'iphone',  w: 5,  v: 40}, {  name: 'mac',  w: 20,  v: 70}]const goodLen = goodList.lengthconst wList = goodList.map(item => {  return item.w})const vList = goodList.map(item => {  return item.v})const nList = goodList.map(item => {  return item.name})const map = {}function getMax(i, j) {  let count = Math.floor(j/wList[i])  if (i === 0) {    map[i] = map[i] || {}    map[i][j] = count    return count * vList[i]  }  if (count === 0) {    map[i] = map[i] || {}    map[i][j] = 0    return getMax(i-1, j)  } else {    let maxIdx = 0    let maxVal = 0    for (let k = 1; k < count + 1; k++) {      let kr = getMax(i - 1, j - wList[i] * k) + vList[i] * k      if (kr > maxVal) {        maxVal = kr        maxIdx = k      }    }    map[i] = map[i] || {}    map[i][j] = maxIdx    return maxVal  }}const val = getMax(goodLen - 1, bag)let bagCost = 0function getSelect(i, j) {  if (i < 0) {    return  }  let count = 0  if (map[i] && map[i][j]) {    count = map[i][j]  }  bagCost += wList[i] * count  console.log(`物品${nList[i]} x ${count}`)  getSelect(i - 1, j - count * wList[i])}getSelect(goodLen - 1, bag)console.log(`总价值${val}`)console.log(`背包负载${bagCost}/${bag}`)// 物品mac x 1// 物品iphone x 8// 物品book x 0// 物品apple x 0// 总价值390// 背包负载60/61

多重背包

• 商品限定重复次数
• 只需要把重复的物品都看作一个不同的物品，然后转化成01背包即可

01背包带路径

const bag = 12const goodList = [{  name: 'apple',  w: 1,  v: 2}, {  name: 'book',  w: 2,  v: 10}, {  name: 'iphone',  w: 5,  v: 40}, {  name: 'mac',  w: 10,  v: 100}]const goodLen = goodList.lengthconst wList = goodList.map(item => {  return item.w})const vList = goodList.map(item => {  return item.v})const nList = goodList.map(item => {  return item.name})const map = {}const path = {}function setMap(i, w, v) {  map[i] = map[i] || {}  map[i][w] = v}function setPath(i, w) {  path[i] = path[i] || {}  // 在重量为w的包里，是否放置第i个物品以达到最大价值  path[i][w] = true}function getMax(i, w) {  if (i === 0) {    if (wList[i] > w) {      setMap(i, w, 0)      return 0    } else {      setMap(i, w, vList[i])      setPath(i, w)      return vList[i]    }  }  if (wList[i] > w) {    let plan = getMax(i-1,w)    setMap(i, w, plan)    return plan  } else {    let planA = getMax(i-1, w)    let planB = getMax(i-1, w-wList[i]) + vList[i]    if (planB > planA) {      setMap(i, w, planB)      setPath(i, w)      return planB    } else {      setMap(i, w, planA)      return planA    }  }}const val = getMax(goodLen - 1, bag)let bagCost = 0function getSelect(i, j) {  if (i < 0) {    return []  }  let arr = []  if (path[i] && path[i][j]) {    arr.push(i)    bagCost += wList[i]    console.log(`物品${nList[i]} x 1`)    return arr.concat(getSelect(i-1, j-wList[i]))  } else {    console.log(`物品${nList[i]} x 0`)    return arr.concat(getSelect(i-1, j))  }}getSelect(goodLen - 1, bag)console.log(`物品总价值${val}`)console.log(`背包负重${bagCost}/${bag}`)// 物品mac x 1// 物品iphone x 0// 物品book x 1// 物品apple x 0// 物品总价值110// 背包负重12/12