-
Notifications
You must be signed in to change notification settings - Fork 33
/
powdered-knapsack.js
68 lines (59 loc) 路 1.59 KB
/
powdered-knapsack.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
/**
* Callback to attach calculated
* property `valueWeightRatio` to an item
* @param {object} item
*/
function addValueWeightRatio({ name, price, weight }) {
let valueWeightRatio = price / weight;
return {
name,
price,
weight,
valueWeightRatio: +valueWeightRatio.toFixed(2)
};
}
/**
* Callback for sorting by value/weight ratio.
* @param {object} a First item
* @param {object} b Second item
*/
function byValueWeightRatio(a, b) {
return b.valueWeightRatio - a.valueWeightRatio;
}
/**
* Creates a copy of list of items with a `valueWeightRatio` property
* and sorts it by that new property.
* @param {Array} items
*/
function sortByValueWeightRatio(items) {
return items.map(addValueWeightRatio).sort(byValueWeightRatio);
}
/**
* Orders the list of items by its value/weight ratio
* and then put them (complete or splitted) in the bag untilg nothing else fits.
* Technique: Heuristics
* @param {Array} items List of items
* @param {number} maxWeight Max weight the bag can carry
*/
function powderedKnapsack(items, maxWeight) {
let bagValue = 0;
let bagWeight = 0;
let bagItems = [];
items = sortByValueWeightRatio(items);
items.forEach(item => {
let availableSpace = maxWeight - bagWeight;
let weight = Math.min(availableSpace, item.weight);
if (weight > 0) {
bagWeight += weight;
bagValue += weight * item.valueWeightRatio;
item.baggedWeight = weight;
bagItems.push(item);
}
})
return {
bagItems,
bagValue
};
}
powderedKnapsack.sortByValueWeightRatio = sortByValueWeightRatio;
module.exports = powderedKnapsack;