TopCoder problem "FibonacciKnapsack" used in SRM 352 (Division I Level Two)



Problem Statement

    

We have n items, each with a specified weight and cost, and a bag that can carry a specified maximum weight. We want to place a subset of these items into the bag such that the total cost is maximized.

Unfortunately, this problem cannot be solved effectively in the general case. However, there are pretty good solutions for some special cases. In this problem, you are required to solve it for the special case where the weights of the items are all Fibonacci numbers.

The first two Fibonacci numbers are 1 and 2. Each successive number is obtained by adding together the two previous numbers. Thus, the first Fibonacci numbers are 1, 2, 3, 5, 8, 13...

You will be given String[] items and a String C. Each element of items describes a single item and is formatted "W P" (quotes for clarity only), where W is the weight of the item and P is the cost. C is the maximum weight that the bag can carry. Return the maximum total cost of the subset of items that can fit into the bag.

 

Definition

    
Class:FibonacciKnapsack
Method:maximalCost
Parameters:String[], String
Returns:long
Method signature:long maximalCost(String[] items, String C)
(be sure your method is public)
    
 

Constraints

-items will contain between 1 and 50 elements, inclusive.
-Each element of items will be formatted "W P" (quotes for clarity only).
-In each element of items, W and P will be integers between 1 and 1016, inclusive, with no leading zeroes.
-Each W will be a Fibonacci number.
-C will represent an integer between 1 and 1016, inclusive, with no leading zeroes.
 

Examples

0)
    
{"5 555", "8 195", "13 651"}
"15"
Returns: 750
We should take the first and the second items. Their total weight is 5+8=13, which does not exceed the maximum capacity of 15, and their total cost is 555+195=750.
1)
    
{"5 555", "8 195", "13 751"}
"15"
Returns: 751
Now it is more profitable to take only the last item with the 751 cost.
2)
    
{"55 1562", "5 814", "55 1962", "8 996", "2 716", "34 1792"}
"94"
Returns: 4568
3)
    
{"13 89"}
"1"
Returns: 0
4)
    
{"27777890035288 9419696870097445", 
 "53316291173 6312623457097563", 
 "165580141 8848283653257131"}
"27777900000000"
Returns: 15160907110354694

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10709&pm=7481

Writer:

Andrew_Lazarev

Testers:

PabloGilberto , brett1479 , Olexiy

Problem categories:

Dynamic Programming, Math