# UVa 10898

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