Winston Hoy revisou este gist 9 years ago. Ir para a revisão
1 file changed, 1 insertion, 1 deletion
cakeThief.js
| @@ -41,7 +41,7 @@ function maxDuffelBagValue (cakeTypes, capacity) { | |||
| 41 | 41 | smallestCake = getSmallestCakeType(validCakeTypes); | |
| 42 | 42 | ||
| 43 | 43 | // until we don't have enough weight left, find the most valuable cake | |
| 44 | - | for (capacityLeft = capacity; capacityLeft >= smallestCake.weight; capacityLeft = bag.getCapacityRemaining()) { | |
| 44 | + | for (var capacityLeft = capacity; capacityLeft >= smallestCake.weight; capacityLeft = bag.getCapacityRemaining()) { | |
| 45 | 45 | // reduce our cakeTypes to the index of the highest value density that can fit | |
| 46 | 46 | let bestCake = validCakeTypes.reduce((prev, next) => { | |
| 47 | 47 | // make sure this next cake will fit | |
Winston Hoy revisou este gist 9 years ago. Ir para a revisão
1 file changed, 1 insertion, 5 deletions
cakeThief.js
| @@ -35,14 +35,13 @@ let cakeTypes = [ | |||
| 35 | 35 | ||
| 36 | 36 | function maxDuffelBagValue (cakeTypes, capacity) { | |
| 37 | 37 | let bag = new Bag(capacity), | |
| 38 | - | capacityLeft = capacity, | |
| 39 | 38 | // clean our cake types to cover out of bounds values | |
| 40 | 39 | validCakeTypes = cleanCakeTypes(cakeTypes), | |
| 41 | 40 | // figure out what the smallest cake is | |
| 42 | 41 | smallestCake = getSmallestCakeType(validCakeTypes); | |
| 43 | 42 | ||
| 44 | 43 | // until we don't have enough weight left, find the most valuable cake | |
| 45 | - | while (capacityLeft >= smallestCake.weight) { | |
| 44 | + | for (capacityLeft = capacity; capacityLeft >= smallestCake.weight; capacityLeft = bag.getCapacityRemaining()) { | |
| 46 | 45 | // reduce our cakeTypes to the index of the highest value density that can fit | |
| 47 | 46 | let bestCake = validCakeTypes.reduce((prev, next) => { | |
| 48 | 47 | // make sure this next cake will fit | |
| @@ -56,9 +55,6 @@ function maxDuffelBagValue (cakeTypes, capacity) { | |||
| 56 | 55 | ||
| 57 | 56 | // add the cake to our bag (adding to its weight and value) | |
| 58 | 57 | bag.addCake(bestCake); | |
| 59 | - | ||
| 60 | - | // re-calculate our remaining cake capacity | |
| 61 | - | capacityLeft = bag.getCapacityRemaining(); | |
| 62 | 58 | } | |
| 63 | 59 | ||
| 64 | 60 | return bag.getValue(); | |
Winston Hoy revisou este gist 9 years ago. Ir para a revisão
1 file changed, 84 insertions
cakeThief.js(arquivo criado)
| @@ -0,0 +1,84 @@ | |||
| 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 | + | } | |
Próximo
Anterior