TopCoder problem "Shopping" used in SRM 331 (Division I Level Two)



Problem Statement

    

Christmas is coming soon and you still have so many things to buy. You are going to the store and don't expect to spend more than X dollars. You want to be able to pay any integer amount not exceeding X dollars, and you want to take as few coins as possible to achieve this.

You are given a int[] values, each element of which describes the dollar value of a kind of coin. You have an unlimited supply of each kind of coin. Return the minimal number of coins you need to take, or -1 if it is impossible to achieve your goal.

 

Definition

    
Class:Shopping
Method:minNumber
Parameters:int, int[]
Returns:int
Method signature:int minNumber(int X, int[] values)
(be sure your method is public)
    
 

Constraints

-X will be between 1 and 1000, inclusive.
-values will contain between 1 and 10 elements, inclusive.
-Each element of values will be between 1 and 1000, inclusive.
-The elements in values will be distinct.
 

Examples

0)
    
20
{1, 2, 5, 10}
Returns: 5
Taking 5 coins with values {1,2,2,5,10} allows you to pay any integer amount between 1 and 20, inclusive.
1)
    
7
{2, 4, 1, 7}
Returns: 3
Here, taking {2,4,1} is enough.
2)
    
20
{2,4,6,8}
Returns: -1
These nominals allow you to pay only even amounts.
3)
    
600
{1,2,3,10,11,30}
Returns: 25

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10011&pm=6479

Writer:

slex

Testers:

PabloGilberto , brett1479 , Olexiy , marian

Problem categories:

Greedy