共计 2743 个字符，预计需要花费 7 分钟才能阅读完成。
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 = 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
