Find the maximum weight that can be collected from a store under given limit

I faced this problem in placement exam of SAP labs:

It's your birthday, so you are given a bag with a fixed space 'S'. You can go to a store and pick as many items you like which can be accommodated inside your bag. The store has 'n' items and each item occupies a space s[i]. You have to find out the maximum space in bag which you can fill.

For example, say the limit of you bag is S = 15 and the store has 10 items of sizes [1, 7, 3, 5, 4, 10, 6, 15, 20, 8]. Now you can fill 15 space by various ways such as [1, 7, 3, 4], [7, 3, 5], [15], [5, 10] and many more. So you return 15.

Note: There is quirk in the sizes of items. All of the items but at most 15 follow the following rule: *for all i, j, either size[i]>=2*size[j]+1 or size[j] >= 2*size[i] +1 if i ≠ j.*

Constraints:

1<= n <= 60.

1<= size[i] <= 10^17.

1<= S <= 10^18.

Example: S = 9, n = 5, sizes = [1, 7, 4, 4, 10].

Output: 8. You can't fill exactly 9 space in any way. You can fill 8 space either by using [1, 7] or [4, 4].

Solution

Let´s call x the elements that follow that rule. Note that for this set of elements, we have some nice properties:

Given x in sorted ascending order, sum(x[i..j]) < x[j + 1]
To solve maximum sum <= k, just iterate in sorted descending order and substract from k x[i] whenever possible. original k - remaining k is the solution. Assuming elements were already sorted, this is O(|x|).

One way to obtain this set is to iterate items sorted by size in ascending order and add to set if :

set has no elements or
current element >= 2 * size[lastElementAdded] + 1

Now we are left with at most 15 items that do not follow this rule. So we can´t use the efficient solving like before. For each item, we can consider to put it or not in the bag. This leads to 2^15 possible sums. For each of those sums, we can run our method for the elements that follow the rule.

Overall complexity: 2^15 * (n - 15). For n = 60, this should be solved in less than a second.

As an exercise: by using accumulated sums and binary search, it can be brought down to 2^15 * log2(n - 15).