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

1. start at weight 0
2. add the first of that item, and add the tastiness to the appropriate weight
3. add the subsequent items eaten and their weight until you hit max weight
4. 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? Consider we have a row right above us with max tastiness for the first n items for a given weight. We know we're going to have to loop through all multiples of kw+i for 0<i<w....so the question is, for a given series, how do we know whether we need to continue off a value in the current row or whether to take the value from the previous row and use the first of this item? At first, you may consider taking whichever is greater, but consider a case where we could take the 5th of this item, or the first of this item....maybe the 5th of this item would be better for this weight, but because of how the weights change, taking the second of this item is better than the sixth.

So ultimately, we have a set of largely arbitrary starting points (weight vs tastiness in the previous row), and a set of identical but shifted parabolae emanating from those points (representing if we started taking items from this row starting at that point). Ultimately, we need to find the upper boundary of the union of these parabolae for all weight. This will be the maximum tastiness for this item (for this set of weights % w....we have to repeat it w times, of course). It turns out we can do this in linear time.

1. we are going to have to find all the intersection points where one parabola supersedes the previous one in tastiness
2. maintain these values in a list sorted by weight
3. when adding a new parabola, there are several situations. It is important to remember the invariant that if a parabola has a higher value and slope at a given point than some other parabola, it will always remain above the other parabola for all points to the right. This only works for identically shaped parabolae, which these all are.
   • if the starting point is above the current maximum, it will remain above the rest of the parabolae for all greater weights. Discard all intersection points greater than this weight
   • if the point is below the current maximum
     • calculate the intersection point with the current rightmost superior parabola
     • If this point is further right than the current right most intersection point, add it to our list of intersections
     • if this point is to the left of the rightmost intersection point, discard the last parabola (since it will no longer ever be maximum) and repeat with the new last parabola

Note that this is linear time, since for a given comparison, either one parabola is added to the set, or one parabola is removed from the set, which makes the number of comparisons strictly bound by 2n.

So now we have a list of parabola and the ranges over which they are maximal. So simply iterate through them and put the right values in our DP table. Repeat for all values %w, and all items.

This solution is correct and the last row will be the maximum tastiness for a given weight using any combination of items.

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