Maximum Subsequence Sum

user_12286830 0
Viewed 2559

Given an array of integers and a threshold value, determine the maximum sum of any subsequence of the array that is less than or equal to the threshold. For all but at most 15 of the elements, either array[i] >= 2*array[j] or array[j] >=2*array[i] where j!=i.

threshold can be up to to 10^17, the length of the array can be up to 60, and array[i] can be up to 10^16.

Here threshold is too high, so we cannot solve it by normal knapsack method. I tried it dividing this array into three parts, then getting lists of possible sums by brute force by backtracking and then merging three lists to find result. But I think there could be a more optimal way of doing this.

knapsack-problem data-structures algorithm
1 Answers

This problem has been carefully set up so that all usual approaches will run out of space. You have to use the hint.

Step 1, sort the array size descending then and divide it into into up to 15 "weird ones" and a chain of elements such that b1 >= 2*b2, b2 >= 2*b3 and so on.

You do that by taking the largest into your chain, then sticking weird ones into the weird array until you find one half the size, add that to the chain, stick weird ones into the weird array, and so on.

Now for each of the up to 32768 subsets of the weird ones, try to figure out which subset of the rest gets you closest. However you can use the following observation. For any element that you have a choice about including, either it is too big to include, or it must be included. (Because if you don't include it, then all the rest together will give you a smaller number.) That gives you a maximum of 45 decision points to consider.

In other words

for each subset of weird ones:
    for each element of the chain
        If we can add this element:
            Add it to the set we are looking at
    if sum(this set) is best so far, improve our max
return the best found.
user_5854110
Related