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. Eat 1 of that item, add to the