[0-1背包问题]有一个背包，背包容量是M=150kg。有7个物品，物品不可以分割成任意大小。（这句很重要）
要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。
物品 A B C D E F G
重量 35kg 30kg 6kg 50kg 40kg 10kg 25kg
价值 10 40 30 50 35 40 30
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<meta http-equiv="X-UA-Compatible" content="ie=edge">
<title>Document</title>
</head>
<body>
<script>
console.time('计时器')
const things = [
{
name: 'A',
weight: 35,
price: 10
},{
name: 'B',
weight: 30,
price: 40
},{
name: 'C',
weight: 6,
price: 30
},{
name: 'D',
weight: 50,
price: 50
},{
name: 'E',
weight: 40,
price: 35
},{
name: 'F',
weight: 10,
price: 40
}, {
name: 'G',
weight: 25,
price: 30
}
],
package = {
things: [],
maxWeight: 150
}
let arr = []
for (let i=0; i<Math.pow(2, things.length); i++) {
arr[i] = []
let v = (i).toString(2).split('').reverse()
things.forEach((el, index) => {
if(v[index] === '1') {
arr[i].push(el)
}
})
}
let newArr = arr.filter((el) => {
let weight = 0
el.forEach((el) => {
weight += el.weight
})
return weight < package.maxWeight
})
newArr.sort((a, b) => {
let price1 = 0,
price2 = 0
a.forEach((el) => {
price1 += el.price
})
b.forEach((el) => {
price2 += el.price
})
return price2 - price1
})
console.timeEnd('计时器')
console.log(newArr);
</script>
</body>
</html>
网友评论