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.