cakeThief.js
· 2.3 KiB · JavaScript
Sin formato
class Bag {
constructor (capacity) {
this.capacity = capacity;
this.cakes = [];
this.weight = 0;
this.value = 0;
}
addCake (cake) {
this.cakes.push(cake);
this.value += cake.value;
this.weight += cake.weight;
}
getCapacityRemaining () {
return this.capacity - this.getWeight();
}
getValue () {
return this.value;
}
getWeight () {
return this.weight;
}
}
let cakeTypes = [
{weight: 7, value: 160},
{weight: 3, value: 90},
{weight: 1, value: 15}
];
// maxDuffelBagValue(cakeTypes, 20);
function maxDuffelBagValue (cakeTypes, capacity) {
let bag = new Bag(capacity),
capacityLeft = capacity,
// clean our cake types to cover out of bounds values
validCakeTypes = cleanCakeTypes(cakeTypes),
// figure out what the smallest cake is
smallestCake = getSmallestCakeType(validCakeTypes);
// until we don't have enough weight left, find the most valuable cake
while (capacityLeft >= smallestCake.weight) {
// reduce our cakeTypes to the index of the highest value density that can fit
let bestCake = validCakeTypes.reduce((prev, next) => {
// make sure this next cake will fit
if (next.weight <= capacityLeft) {
// decide which is higher value-weight ratio
return prev.value / prev.weight > next.value / next.weight ? prev : next;
}
// this next cake doesn't fit, keep the previous
else return prev;
}, {value: 0, weight: 1});
// add the cake to our bag (adding to its weight and value)
bag.addCake(bestCake);
// re-calculate our remaining cake capacity
capacityLeft = bag.getCapacityRemaining();
}
return bag.getValue();
}
/**
* reduce our cakeType collection down to one with the lowest weight
* @param {array} cakeTypes - collection of cakeType object {weight, value}
* @return {object} cakeType
*/
function getSmallestCakeType (cakeTypes) {
return cakeTypes.reduce((prev, next) => prev.weight < next.weight ? prev : next);
}
/**
* cleanCakeTypes - filters out invalid cakeTypes
* @param {array} cakeTypes - collection of cakeType object {weight, value}
* @return {array} filtered collection of cakeType objects
*/
function cleanCakeTypes (cakeTypes) {
// filter out any cake types with weight or value of 0, that's unreal!
return cakeTypes.filter((type) => type.weight > 0 && type.value > 0);
}
| 1 | class Bag { |
| 2 | constructor (capacity) { |
| 3 | this.capacity = capacity; |
| 4 | this.cakes = []; |
| 5 | this.weight = 0; |
| 6 | this.value = 0; |
| 7 | } |
| 8 | |
| 9 | addCake (cake) { |
| 10 | this.cakes.push(cake); |
| 11 | this.value += cake.value; |
| 12 | this.weight += cake.weight; |
| 13 | } |
| 14 | |
| 15 | getCapacityRemaining () { |
| 16 | return this.capacity - this.getWeight(); |
| 17 | } |
| 18 | |
| 19 | getValue () { |
| 20 | return this.value; |
| 21 | } |
| 22 | |
| 23 | getWeight () { |
| 24 | return this.weight; |
| 25 | } |
| 26 | } |
| 27 | |
| 28 | let cakeTypes = [ |
| 29 | {weight: 7, value: 160}, |
| 30 | {weight: 3, value: 90}, |
| 31 | {weight: 1, value: 15} |
| 32 | ]; |
| 33 | |
| 34 | // maxDuffelBagValue(cakeTypes, 20); |
| 35 | |
| 36 | function maxDuffelBagValue (cakeTypes, capacity) { |
| 37 | let bag = new Bag(capacity), |
| 38 | capacityLeft = capacity, |
| 39 | // clean our cake types to cover out of bounds values |
| 40 | validCakeTypes = cleanCakeTypes(cakeTypes), |
| 41 | // figure out what the smallest cake is |
| 42 | smallestCake = getSmallestCakeType(validCakeTypes); |
| 43 | |
| 44 | // until we don't have enough weight left, find the most valuable cake |
| 45 | while (capacityLeft >= smallestCake.weight) { |
| 46 | // reduce our cakeTypes to the index of the highest value density that can fit |
| 47 | let bestCake = validCakeTypes.reduce((prev, next) => { |
| 48 | // make sure this next cake will fit |
| 49 | if (next.weight <= capacityLeft) { |
| 50 | // decide which is higher value-weight ratio |
| 51 | return prev.value / prev.weight > next.value / next.weight ? prev : next; |
| 52 | } |
| 53 | // this next cake doesn't fit, keep the previous |
| 54 | else return prev; |
| 55 | }, {value: 0, weight: 1}); |
| 56 | |
| 57 | // add the cake to our bag (adding to its weight and value) |
| 58 | bag.addCake(bestCake); |
| 59 | |
| 60 | // re-calculate our remaining cake capacity |
| 61 | capacityLeft = bag.getCapacityRemaining(); |
| 62 | } |
| 63 | |
| 64 | return bag.getValue(); |
| 65 | } |
| 66 | |
| 67 | /** |
| 68 | * reduce our cakeType collection down to one with the lowest weight |
| 69 | * @param {array} cakeTypes - collection of cakeType object {weight, value} |
| 70 | * @return {object} cakeType |
| 71 | */ |
| 72 | function getSmallestCakeType (cakeTypes) { |
| 73 | return cakeTypes.reduce((prev, next) => prev.weight < next.weight ? prev : next); |
| 74 | } |
| 75 | |
| 76 | /** |
| 77 | * cleanCakeTypes - filters out invalid cakeTypes |
| 78 | * @param {array} cakeTypes - collection of cakeType object {weight, value} |
| 79 | * @return {array} filtered collection of cakeType objects |
| 80 | */ |
| 81 | function cleanCakeTypes (cakeTypes) { |
| 82 | // filter out any cake types with weight or value of 0, that's unreal! |
| 83 | return cakeTypes.filter((type) => type.weight > 0 && type.value > 0); |
| 84 | } |