Connection Status:
Competition Arena > TreasuresPacking

TreasuresPacking

SRM 308 · 2006-06-24 · by Andrew_Lazarev

SRM 308 · 2006-06-24 · by Andrew_Lazarev · Dynamic Programming, String Parsing
Class Name: TreasuresPacking
Return Type: double
Method Name: maximizeCost
Arg Types: (vector<string>, int)
Problem Statement

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.

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
4)
{"1 1 Y"}
10000
Returns: 1.0

Submissions are judged against all 123 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class TreasuresPacking with a public method double maximizeCost(vector<string> treasures, int W) · 123 test cases · 2 s / 256 MB per case

Submitting as anonymous