TopCoder problem "Fuses" used in TCO05 Qual 4/6 (Division I Level Three)



Problem Statement

    Homes typically have 20 amp fuses in their fuseboxes. Appliances are then hooked up to the fuses. If the appliances connected to a single fuse ever draw more than 20 amps, the fuse will blow (which you would like to avoid). In large homes with a large number of appliances, multiple 20 amp fuses may be required to accommodate all of the appliances. You have a number of large appliances, each of which must be connected to some fuse. The number of amps used by each appliance will be given by amps. Your task is to find the minimum number of 20 amp fuses that can accommodate all of the appliances.
 

Definition

    
Class:Fuses
Method:minFuses
Parameters:int[]
Returns:int
Method signature:int minFuses(int[] amps)
(be sure your method is public)
    
 

Constraints

-Each element of amps will be between 1 and 10, inclusive.
-amps will contain between 1 and 10 elements, inclusive.
 

Examples

0)
    
{10,10}
Returns: 1
We can hook up two 10 amp appliances to one 20 amp fuse.
1)
    
{10,10,10,10,10,10,10,10,10,10}
Returns: 5
Here we require five 20 amp fuses. We hook up two appliances to each one.
2)
    
{4,4,8,9,9,10}
Returns: 3

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=8023&pm=4725

Writer:

lars2520

Testers:

PabloGilberto , brett1479 , Olexiy

Problem categories:

Brute Force, Recursion