javascript算法基础之01背包，完全背包，多重背包实现

seanlook 发布于2019-08-23 14:25 / 3077人阅读

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

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

const bag = 61

const 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.length

const 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 = 0
function 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 = 12
const 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.length

const 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 = 0

function 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

云服务器 GPU云服务器 php 实现背包算法背包c语言实现背包算法 c语言递归背包问题

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/100587.html

背包问题学习笔记

摘要：状态转移方程背包问题的状态转移方程是其中即表示前件物品恰放入一个容量为的背包可以获得的最大价值。求解将哪些物品装入背包可使这些物品的体积总和不超过背包容量，且价值总和最大。 01背包 01背包的概念有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。从这个题目中可以看出，01背包的特点就是：每种物品仅有一件，可以选择放或...

xiao7cn 2019-08-20 18:05 评论0 收藏0
01背包问题（动态规划算法）

摘要：背包问题题目给定种物品和一个容量为的背包，物品的体积是，其价值为。用子问题定义状态其状态转移方程是。 P01: 01背包问题题目给定 N 种物品和一个容量为 V 的背包，物品 i 的体积是 wi，其价值为 ci 。(每种物品只有一个)问：如何选择装入背包的物品，使得装入背包中的物品的总价值最大？面对每个物品，我们只有选择放入或者不放入两种选择，每种物品只能放入一次。我们用之前同...

tuniutech 2019-08-23 10:52 评论0 收藏0
经典动态规划--01背包问题

摘要：背包问题具体例子假设现有容量的背包，另外有个物品，分别为，，。最后，就是动态规划的思路了。而前个物体放入容量为的背包，又可以转化成前个物体放入背包的问题。背包问题具体例子：假设现有容量10kg的背包，另外有3个物品，分别为a1，a2，a3。物品a1重量为3kg，价值为4；物品a2重量为4kg，价值为5；物品a3重量为5kg，价值为6。将哪些物品放入背包可使得背包中的总价值最大？首先...

warkiz 2019-08-19 11:06 评论0 收藏0
王者编程大赛之三 — 01背包

摘要：动态规划概念动态规划过程每次决策依赖于当前状态，又随即引起状态的转移。相关文章王者编程大赛之一王者编程大赛之二蓄水池王者编程大赛之四约瑟夫环王者编程大赛之五最短路径首发于樊浩柏科学院服务目前每月会对搬家师傅进行评级，根据师傅的评级排名结果，我们将优先保证最优师傅的全天订单。 showImg(https://img3.fanhaobai.com/2017/12/2017-ziro...

Cympros 2019-07-01 12:36 评论0 收藏0
遗传算法解背包问题（javascript实现）

摘要：遗传算法物竞天择，适者生存，遗传算法就是借鉴生物体自然选择和自然遗传机制的随机搜索算法。随机生成的基因适应度的最大值随机生成，适应度函数计算种群中所有对象的适应度及总和，并对超出的基因进行惩罚。此为《算法的乐趣》读书笔记，我用javascript（ES6）重新实现算法。遗传算法物竞天择，适者生存，遗传算法就是借鉴生物体自然选择和自然遗传机制的随机搜索算法。算法的关键点有：基因的选...

longshengwang 2019-08-19 18:10 评论0 收藏0