Connection Status:
Competition Arena > FibonacciKnapsack

FibonacciKnapsack

SRM 352 · 2007-06-02 · by Andrew_Lazarev

SRM 352 · 2007-06-02 · by Andrew_Lazarev · Dynamic Programming, Math
Class Name: FibonacciKnapsack
Return Type: long
Method Name: maximalCost
Arg Types: (vector<string>, string)
Problem Statement

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.

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)
{"32951280099 34851840182","53316291173 52855220864","86267571272 86275432313","139583862445 140310964457","225851433717 224839833662","365435296162 367555122387","591286729879 589330020334","956722026041 955600572711","1548008755920 1548165267794","2504730781961 2503718362316","4052739537881 4051396608386","6557470319842 6559347353150","10610209857723 10610100492663","17167680177565 17169683238048","27777890035288 27779743264551","44945570212853 44943549937426","72723460248141 72724071593594","117669030460994 117666914238211","190392490709135 190393337129114","308061521170129 308063274753980","498454011879264 498451999372857","806515533049393 806515194345674","1304969544928657 1304967939925373","2111485077978050 2111486709071689","3416454622906707 3416452570156355","5527939700884757 5527938309376261","8944394323791464 8944394973262345","1 1","2 2","3 3","5 5","8 8","13 14","21 23","34 31","55 51","89 85","144 148","233 243","377 372","610 600","987 960","1597 1490","2584 2741","4181 4542","6765 7095","10946 11116","17711 16508","28657 27430","46368 48041"}
"10000000000000000"
Returns: 9999996514303784

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

Coding Area

Language: C++17 · define a public class FibonacciKnapsack with a public method long long maximalCost(vector<string> items, string C) · 138 test cases · 2 s / 256 MB per case

Submitting as anonymous