Buffed Buffet
This problem is diabolical. It took me a couple weeks to figure out how to do it....especially since at first glance it seems pretty simple. You have two SEEMINGLY simple problems that you could probably solve on your own, but then you have to combine them to come up with an optimal solution. That part gets tricky.
So first lets consider how to solve them on their own.
Continuous Problem
This one is the easiest to solve on its own. You greedily choose the one with the most tastiness, and eat it until some other food becomes more tasty, at which point you eat both foods together. The combined function here is to eat weight of each in proportion inverse to their slopes (the one that decreases less, you eat more of). And then you have to calculate the new slope to. This is just a bit of math.
Discrete Problem
This one is trickier. It may seem that greedy is the right answer here, since it's just discrete? right? Well...no....since we can't take parts of an item, we might put ourselves in a non-optimal weight situation by choosing the tastiest item...so that we can't fill the rest of the weight with more tasty items. If you expanded out the weights of all items, this would literally be knapsack...but that would also be far too many items to run knapsack with.
Either way, it's clear we're going to have to do some DP sort of thing. One thought would be for every weight, try to add one of every remaining item. The problem here is that we'd have to have the number of each item we'd eaten in our state...which explodes the state...no-go.
The solution goes by how you order the DP. If we go by weight, and THEN item, then we have to remember how many of each item we used...what if instead we go by item THEN weight. So for each item
- start at weight 0
- add the first of that item, and add the tastiness to the appropriate weight
- add the subsequent items eaten and their weight until you hit max weight
- when you've finished this, row 0 of your DP matrix should have an entry every W0 weights with the total tastiness if you had eaten that weight of the first item
Okay, so now how do we do it for subsequent items?
- start at weight 0, and add in all numbers of this item as we did in the first step, but base it off the tastiness of the tastiness of that starting weight from the previous item
- repeat this process, but starting at weights 1 through max. If we run into a situation where we get an EQUAL tastiness as was already in the box for this row, replace it, since we will do better when we eat the next piece of this item, and using fewer of an item to get to a given tastiness and weight must be better
- repeat this for all items moving forward, again using the previous item/weights for base values to start adding to
This solution is correct and the last row will be the maximum tastiness for a given weight using any combination of items....but what about runtime?
Since every item has to run it's algorithm starting at every weight, and could potentially have to iterate through the end of the weight....so O(NW^2)...oof too slow. Turns out minor optimizations like starting at the highest weight and working backwards doesn't really work, since we can still run into worst case.
Solution:
- start at weight 0, and iterate through mutliples of W, but before blindly adding the weight of whichever amount of this item we'd have to, check if it would instead be better to eat a NEW one of this item, if so do that instead, and continue on iterating through multiples of W with the new "reset"
- repeat for weights 1->W-1
This works because as before, it's always better to use fewer amounts of the item we are on for a given weight...but we figure that out on the fly instead of going all the way to the end of the array with work we'll end up tossing out later.
Since we only evaluate each weight for a given item once, it makes our total runtime O(N*W)
Combining
Iterate over all possible weights, assign that much weight to the discrete solution (which we have from the DP), and fill the rest with continuous. Take the largest