TopCoder problem "GreedyChange" used in TCCC '03 Round 3 (Division I Level Two)



Problem Statement

    

Many monetary systems have the nice property that, when giving change, a greedy algorithm will always produce the fewest number of coins possible. In other words, if you are trying to produce a certain amount of change, then something like the following algorithm will produce the fewest coins possible:

number of coins = 0;
while(amount>0){
	find the largest coin, c, that is less than or equal to amount;
	subtract the value of c from amount and increment the number of coins;
}

For example, the American monetary system with coins valued at 1, 5, 10, and 25 cents has this property. However, it is not difficult to construct values of coins that do not have this property. If the values of your coins are 1, 3 and 4, then you can make 6 with two 3's. The algorithm above, on the other hand, will use 3 coins - a 4 and two 1's.

Your task is to write a class GreedyChange, with a method smallest that takes a int[], denominations, representing the values of the various coins in some monetary system. You should return the smallest amount of money for which the greedy algorithm does not produce the fewest coins possible. If the greedy algorithm always produces the fewest coins possible, return -1. To guarantee that the greedy algorithm always works (terminates), there will always be a coin worth 1.

 

Definition

    
Class:GreedyChange
Method:smallest
Parameters:int[]
Returns:int
Method signature:int smallest(int[] denominations)
(be sure your method is public)
    
 

Constraints

-denominations will contain between 1 and 50 elements, inclusive.
-Each element of denominations will be between 1 and 500,000, inclusive.
-At least one of the elements of denominations will be 1.
 

Examples

0)
    
{1,25,10,5}
Returns: -1
In this system, the greedy algorithm always produces an optimal result.
1)
    
{1,3,4}
Returns: 6
If we need to make 6, the greedy algorithm does so as 4 + 1 + 1. However, the optimal solution is 3 + 3.
2)
    
{1,10,10,20,25}
Returns: 30
Note that elements may be repeated.
3)
    
{1,15,25}
Returns: 30
4)
    
{1,2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,32,34,36,38,40,42,44,46,48,50,
52,54,56,58,60,62,64,66,68,70,72,74,76,78,80,82,84,86,88,90,92,94,96,500000}
Returns: -1
5)
    
{500000,499999,1}
Returns: 999998

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=1579

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=4474&pm=1579

Writer:

lars2520

Testers:

brett1479 , schveiguy

Problem categories:

Advanced Math, Dynamic Programming