UVa 11517

From Algorithmist
Jump to navigation Jump to search

11517 - Exact Change[edit]

Summary[edit]

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[edit]

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] = 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[edit]

int dp[30001];

dp[0] = 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);

Input[edit]

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[edit]

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

Solutions[edit]

Category[edit]

Dynamic Programming
Coin Change