# UVa 10898

## Summary

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

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 ${\displaystyle O(10^{6})}$, definitely small enough.

Basically, the recurrence is simply:

${\displaystyle Best(x_{1},x_{2},\ldots ,x_{6})=\min _{i=1,\ldots ,N}(Best(x_{1}-c_{i,1},x_{2}-c_{i,2},\ldots ,x_{6}-c_{i,6})+p_{i})}$

where ${\displaystyle x_{1},x_{2},\ldots ,x_{6}}$ are simply the items, ${\displaystyle c_{i,1},c_{i,2},\ldots ,c_{i,6}}$ are the number of items in a given combo ${\displaystyle i}$, and ${\displaystyle p_{i}}$ is the price of that given combo.

## Implementations

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

## Input

```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
```

```4139
4700
```