2

This is the source of the problem at uva.onlinejudge.org

The problem basically says:
Given N amount of money which has to be given!! we need to find out how much minimum coins we can give and the total value of those coins such that the extra amount given is minimal using n given denominations!

For example:

1400 -> N 
3    -> no of denominations 
500 
1000 
2000

Output: 1500 2

My question is:
What are the overlapping subproblems here?

I mean:
Are there any overlapping subproblems?
Because I couldn't find any...

zx485
  • 28,498
  • 28
  • 50
  • 59
Harjot Atwal
  • 33
  • 4

1 Answers1

0

The overlapping sub-problems are the minimum number of coins/bills to sum to a particular number of cents.

for coin_value in coins(sorted)
   for sum where num[sum] is valid
      num[ sum + coin_value ] = Min( num[sum + coin_value], num[sum] + 1 )

See: Dynamic Programming Coin Change Limited Coins

The constraints to the problem are low enough you can use the accepted answer to that question. The only difference is that you calculate the minimum number of coins/bills to sum up to the target price, and then you continue going past the target price. When you are done filling in the array, start at the target price and go up until you find a valid answer.

Sort the coins/bills and start with the largest denomination and go down.

(My solution was accepted on UVa.)

Mark Wistrom
  • 161
  • 1
  • 6