Skip to content

Instantly share code, notes, and snippets.

@curiousercreative
Last active November 10, 2016 22:13
Show Gist options
  • Save curiousercreative/0acaa9a2ca07225c76790d976a41d6c4 to your computer and use it in GitHub Desktop.
Save curiousercreative/0acaa9a2ca07225c76790d976a41d6c4 to your computer and use it in GitHub Desktop.
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),
// 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
for (var capacityLeft = capacity; capacityLeft >= smallestCake.weight; capacityLeft = bag.getCapacityRemaining()) {
// 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);
}
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);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment