TopCoder problem "LoadBalancing" used in SRM 209 (Division II Level Three)



Problem Statement

    The scientific program ITES runs on a computer with two CPUs. The input data for ITES consists of chunks of different sizes, and each chunk has to be processed in whole by either of the CPUs. The chunks may also be processed in any order. Both CPUs run at the same speed and require 1 second of time to process any 1 kilobyte of data.



You are given a int[] chunkSizes containing the sizes of the different input chunks in kilobytes. Due to the method by which the input data is gathered, all sizes are multiples of 1024. Return the fastest time in seconds in which all the input can be processed.
 

Definition

    
Class:LoadBalancing
Method:minTime
Parameters:int[]
Returns:int
Method signature:int minTime(int[] chunkSizes)
(be sure your method is public)
    
 

Notes

-Reminder: Your method may use at most 64 megabytes of memory.
 

Constraints

-chunkSizes contains between 0 and 50 elements, inclusive.
-Each element of chunkSizes is between 1024 and 4194304, inclusive.
-Each element of chunkSizes is a multiple of 1024.
 

Examples

0)
    
{3072, 3072, 7168, 3072, 1024}
Returns: 9216
One CPU gets assigned the chunks of size 7168 and 1024 and requires 8192 seconds to process them, the other CPU gets assigned the three chunks of size 3072 and requires 9216 seconds to process them.
1)
    
{2048}
Returns: 2048
2)
    
{2048, 1024, 1024, 2048}
Returns: 3072
3)
    
{4194304, 4194304, 4194304, 4194304, 4194304,
 4194304, 4194304, 4194304, 4194304, 4194304,
 4194304, 4194304, 4194304, 4194304, 4194304,
 4194304, 4194304, 4194304, 4194304, 4194304,
 4194304, 4194304, 4194304, 4194304, 4194304,
 4194304, 4194304, 4194304, 4194304, 4194304,
 4194304, 4194304, 4194304, 4194304, 4194304,
 4194304, 4194304, 4194304, 4194304, 4194304,
 4194304, 4194304, 4194304, 4194304, 4194304,
 4194304, 4194304, 4194304, 4194304, 4194304}
Returns: 104857600

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=5855&pm=2947

Writer:

Wernie

Testers:

PabloGilberto , lbackstrom , brett1479

Problem categories:

Dynamic Programming