# UVa 11517

## Summary

Given n bills (or coins) of certain values. Select a subset of them so that the total value is at least P and is minimum.

## Explanation

Use Dynamic Programming to determine whether there is a way to make a value V from the n bills.

Let dp[X] be the number of bills needed to make a value of X.

To fill in this DP table, first set dp = 0 and set the rest to INFINITY.

For each bill with value C, update dp[v+C] = min(dp[v+C], dp[v]+1) for all value v where dp[v] is not INFINITY.

The answer is X and dp[X], where X >= P and dp[X] is not INFINITY and X is minimum. To find such X, a simple iteration will do.

## Implementations

```int dp;

dp = 0;
for (int i=1; i<=30000; i++)
dp[i] = INFINITE;

for each coin C do
for (int v = 30001 - C - 1; v >= 0; v--)
if (dp[v] < INFINITE)
dp[v+C] = min(dp[v+C], dp[v]+1);
```

```9
1400
3
500
1000
2000
12
5
1
2
2
2
5
4
4
2
1
1
1
20
4
4
4
5
10
1
2
1
1
2
1
3
1000
10
10
900
20
200
300
400
10
10
20
20
13
5
9
5
2
3
3
10000
5
10000
10000
10000
10000
10000
```

## Output

```1500 2
12 5
4 3
23 4
1 1
3 1
1100 2
13 4
10000 1
```

## Category

```Dynamic Programming
Coin Change
```