10898 - Combo Deal
It's an optimization problem that deals with minimizing the cost given a set of items to purchase and combos that are cheaper than the individual items. Given the small constraints, the problem is easy to use dynamic programming to solve.
Use Dynamic Programming on the (up to) six items. Since there can at most be 9 requests, that means the space we're searching is at most , definitely small enough.
Basically, the recurrence is simply:
where are simply the items, are the number of items in a given combo , and is the price of that given combo.
Some can easily make it simplier by using a 6 digit decimal number - one for each item in the given function.
4 349 99 109 219 2 1 1 1 0 479 2 2 2 1 999 2 9 6 8 0 9 6 8 5