最近看到一个挺有意思的算法，记录于此。
有 N 件物品和一个容量是 V 的背包。每件物品有且只有一件。
第 i 件物品的体积是 v[i] ，价值是 w[i] 。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
示例 1：
输入: N = 3, V = 4, v = [4,2,3], w = [4,2,3]
输出: 4
解释: 只选第一件物品，可使价值最大。
示例 2：
输入: N = 3, V = 5, v = [4,2,3], w = [4,2,3]
输出: 5
解释: 不选第一件物品，选择第二件和第三件物品，可使价值最大。
自己的解法
思路：列出所有组合，根据组合计算最大价格。
- 计算所有可能存在的组合
- 计算前先做了功课，学习到了全排列算法的一种解法。参考地址
let func = (arr) => {
let len = arr.length
let res = [] // 所有排列结果
/**
* 【全排列算法】
* 说明：arrange用来对arr中的元素进行排列组合，将排列好的各个结果存在新数组中
* @param orderArr：排列好的元素
* @param restArr：待排列元素
*/
let arrange = (orderArr, restArr) => {
if (orderArr.length === len) {
res.push(orderArr)
} else {
restArr.forEach((item, index) => {
let newRestArr = [...restArr] // 复制一份待排列数组
newRestArr.splice(index, 1) // 从待排列数组中将当前元素删除，获取到新的待排列数组
arrange(orderArr.concat(item), newRestArr) // 递归排列：① 当前项拼接在已排列数组的后面 ②剩余数组待处理
})
}
}
arrange([], arr)
return res
}
console.log('结果：', func(['A', 'B', 'C', 'D']))
先模拟只有两个选项['A','B']的排列过程，再模拟有三个选项['A','B','C']的排列过程。
理解了['A','B','C']的排列过程，就可以总结出规律。
- 以上是全排列，而我们需要的是不重复的组合排列，将
newRestArr.splice(index, 1)改为截取当前往后的数组，去掉组合长度必须为数组长度的限制即可。
const packageFn = (arr) => {
let res = []
let getConbine = (orderArr, restArr) => {
if (orderArr.length) {
res.push(orderArr)
}
restArr.forEach((item, index) => {
let newRestArr = [...restArr].slice(index + 1)
getConbine(orderArr.concat(item), newRestArr)
})
}
getConbine([], arr)
return res
}
console.log(packageFn(['A', 'B', 'C', 'D']))
- 最后回到背包问题，计算组合方式，根据价格排序，返回最大价值的组合。
const packageFn = (ws, vs, V) => {
// 获取所有不超出容量的组合
let getConbine = (orderArr, restArr) => {
let orderWeight = getWeight(orderArr)
if (orderArr.length) {
res.push(orderArr)
}
restArr.forEach((item, i) => {
let newRestArr = [...restArr].slice(i + 1)
if (orderWeight + item.weight <= V) { // 不超出总重量才会循环下去
getConbine(orderArr.concat(item), newRestArr)
}
});
}
// 计算重量
const getWeight = (arr) => {
return arr.reduce((total, cur) => total + cur.weight, 0)
}
// 计算价格
const getPrice = (arr) => {
return arr.reduce((total, cur) => total + cur.price, 0)
}
let res = []
let wvArr = ws.map((item, index) => {
return {
index: index,
weight: item,
price: vs[index]
}
});
getConbine([], wvArr) // 获取所有不超出容量的组合
// console.log(res)
res.sort((a, b) => { // 按价格排序
return getPrice(b) - getPrice(a)
})
return res[0]
}
var ws = [2, 2, 6, 5, 4], vs = [6, 3, 5, 4, 6], V = 10
console.log(packageFn(ws, vs, V))
递归解法
解法来源于https://segmentfault.com/a/1190000012829866，具体看这篇文章吧，没有第一步的解析，也没法理解以下的代码。
function knapsack(n, W, weights, values, selected) {
if (n == 0 || W == 0) {
//当物品数量为0，或者背包容量为0时，最优解为0
return 0;
} else {
//从当前所剩物品的最后一个物品开始向前，逐个判断是否要添加到背包中
for (var i = n - 1; i >= 0; i--) {
//如果当前要判断的物品重量大于背包当前所剩的容量，那么就不选择这个物品
//在这种情况的最优解为f(n-1,C)
if (weights[i] > W) {
return knapsack(n - 1, W, weights, values, selected);
} else {
var a = knapsack(n - 1, W, weights, values, selected); //不选择物品i的情况下的最优解
var b = values[i] + knapsack(n - 1, W - weights[i], weights, values, selected); //选择物品i的情况下的最优解
//返回选择物品i和不选择物品i中最优解大的一个
if (a > b) {
selected[i] = 0; //这种情况下表示物品i未被选取
return a;
} else {
selected[i] = 1; //物品i被选取
return b;
}
}
}
}
}
var selected = [], ws = [2,2,6,5,4], vs = [6,3,5,4,6]
var b = knapsack( 5, 10, ws, vs, selected)
console.log(b) //15
selected.forEach(function(el,i){
if(el){
console.log("选择了物品"+i+ " 其重量为"+ ws[i]+" 其价值为"+vs[i])
}
})
