Just [[currentUser.getNumFreeQuestionsLeft()]] No more free questions left!Upgrade Now
You are a renowned thief who has recently switched from stealing precious metals to stealing cakes because of the insane profit margins. You end up hitting the jackpot, breaking into the world's largest privately owned stock of cakes—the vault of the Queen of England.
While Queen Elizabeth has a limited number of types of cake, she has an unlimited supply of each type.
Each type of cake has a weight and a value, stored in a tuple with two indices:
You brought a duffel bag that can hold limited weight, and you want to make off with the most valuable haul possible.
Write a function max_duffel_bag_value that takes a list of cake type tuples and a weight capacity, and returns the maximum monetary value the duffel bag can hold.
Weights and values may be any non-negative integer. Yes, it's weird to think about cakes that weigh nothing or duffel bags that can't hold anything. But we're not just super mastermind criminals—we're also meticulous about keeping our algorithms flexible and comprehensive.
Does your function work if the duffel bag's weight capacity is 0 kg?
Does your function work if any of the cakes weigh 0 kg? Think about a cake whose weight and value are both 0!
We can do this in time and space, where n is the number of types of cakes and k is the duffel bag's capacity!
time, and space, where n is number of types of cake and k is the capacity of the duffel bag. We loop through each cake (n cakes) for every capacity (k capacities), so our runtime is , and maintaining the a list of k+1 capacities gives us the space.
Congratulations! Because of dynamic programming, you have successfully stolen the Queen's cakes and made it big.
Keep in mind: in some cases, it might not be worth using our optimal dynamic programming solution. It's a pretty slow algorithm—without any context (not knowing how many cake types we have, what our weight capacity is, or just how they compare) it's easy to see potentially being as bad as if n is close to k.
If we cared about time, like if there was an alarm in the vault and we had to move quickly, it might be worth using a faster algorithm that gives us a good answer, even if it's not always the optimal answer. Some of our first ideas in the breakdown were to look at cake values or value/weight ratios. Those algorithms would probably be faster, taking time (we'd have to start by sorting the input).
Sometimes an efficient, good answer might be more practical than an inefficient, optimal answer.