UVa 10898

From Algorithmist
Jump to navigation Jump to search

10898 - Combo Deal[edit]

Summary[edit]

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.

Explanation[edit]

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.

Implementations[edit]

Some can easily make it simplier by using a 6 digit decimal number - one for each item in the given function.

Input[edit]

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

Output[edit]

4139
4700