TopCoder problem "TreasuresPacking" used in SRM 308 (Division II Level Three)



Problem Statement

    

You have found a cave filled with treasures, and you want to take as much as you can. However, you can only make one trip, so you decide to use the following strategy. You will take the treasures with the maximal total cost, but with a total weight no greater than W. Each treasure is characterized by its weight, cost, and whether it can be divided. For example, a bar of gold can be divided into two smaller bars of any size (with costs proportional to the cost of the original bar), but a cut-glass bowl cannot be divided because it would become worthless.

You will be given a String[] treasures and an int W. Each element of treasures will be formatted as "weight cost can_be_divided" (quotes for clarity), where weight and cost are integers and can_be_divided is either 'Y' or 'N'. Return the total cost of the treasures you will take.

 

Definition

    
Class:TreasuresPacking
Method:maximizeCost
Parameters:String[], int
Returns:double
Method signature:double maximizeCost(String[] treasures, int W)
(be sure your method is public)
    
 

Notes

-Your return value must have an absolute or relative error less than 1e-9.
 

Constraints

-W will be between 1 and 10000, inclusive.
-treasures will contain between 1 and 50 elements, inclusive.
-Each element of treasures will be formatted as described in the problem statement.
-Each integer in treasures will contain no leading zeroes.
-The weight of each treasure will be between 1 and 10000, inclusive.
-The cost of each treasure will be between 1 and 10000, inclusive.
 

Examples

0)
    
{"100 100 N", "100 100 N", "130 10 Y"}
150
Returns: 103.84615384615384
We can't take both of the expensive treasures because their total weight is 200, which is greater than W, and neither one can be divided. So, we take one of the expensive treasures along with 50/130 of the cheaper dividable treasure to maximize the total cost.
1)
    
{"100 100 N", "100 100 N", "100 1000 Y"}
150
Returns: 1000.0
2)
    
{"207 1459 Y", "150 6867 N", "694 3494 Y", "417 7479 N"}
650
Returns: 14931.00966183575
3)
    
{"350 2765 Y", "258 560 Y", "120 9325 N", "879 302 Y",
 "611 2674 Y", "774 2273 Y", "318 1572 Y"}
3301
Returns: 19467.907849829353

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=9988&pm=6476

Writer:

Andrew_Lazarev

Testers:

PabloGilberto , brett1479 , vorthys , Olexiy

Problem categories:

Dynamic Programming, String Parsing