Last active
October 1, 2020 13:04
-
-
Save wladimir/28109527cd08b3f1bb4dc8c4e40973af to your computer and use it in GitHub Desktop.
Cake Thief
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public static class InfinityException extends RuntimeException { | |
public InfinityException() { | |
super("Max value is infinity!"); | |
} | |
} | |
public static long maxDuffelBagValue(CakeType[] cakeTypes, int weightCapacity) { | |
// we make an array to hold the maximum possible value at every | |
// duffel bag weight capacity from 0 to weightCapacity | |
// starting each index with value 0 | |
long[] maxValuesAtCapacities = new long[weightCapacity + 1]; | |
for (int currentCapacity = 0; currentCapacity <= weightCapacity; currentCapacity++) { | |
// set a variable to hold the max monetary value so far for currentCapacity | |
long currentMaxValue = 0; | |
for (CakeType cakeType : cakeTypes) { | |
// if a cake weighs 0 and has a positive value the value of our duffel bag is infinite! | |
if (cakeType.weight == 0 && cakeType.value != 0) { | |
throw new InfinityException(); | |
} | |
// if the current cake weighs as much or less than the current weight capacity | |
// it's possible taking the cake would get a better value | |
if (cakeType.weight <= currentCapacity) { | |
// so we check: should we use the cake or not? | |
// if we use the cake, the most kilograms we can include in addition to the cake | |
// we're adding is the current capacity minus the cake's weight. we find the max | |
// value at that integer capacity in our array maxValuesAtCapacities | |
long maxValueUsingCake = cakeType.value | |
+ maxValuesAtCapacities[currentCapacity - cakeType.weight]; | |
// now we see if it's worth taking the cake. how does the | |
// value with the cake compare to the currentMaxValue? | |
currentMaxValue = Math.max(maxValueUsingCake, currentMaxValue); | |
} | |
} | |
// add each capacity's max value to our array so we can use them | |
// when calculating all the remaining capacities | |
maxValuesAtCapacities[currentCapacity] = currentMaxValue; | |
} | |
return maxValuesAtCapacities[weightCapacity]; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment