Smallest sum of subarray with sum greater than a given value

Question

Input: Array of N positive numbers and a value X such that N is small compared to X
Output: Subarray with sum of all its numbers equal to Y > X, such that there is no other subarray with sum of its numbers bigger than X but smaller than Y.

Is there a polynomial solution to this question? If so, can you present it?

Answer 1

As the other answers indicate this is a NP-Complete problem which is called the "Knapsack Problem". So there is no polynomial solution. But it has a pseudo polynomial time algorithm. This explains what pseudo polynomial is.

A visual explanation of the algorithm.

And some code.

If this is work related (I met this problem a few times already, in various disguises) I suggest introducing additional restrictions to simplify it. If it was a general question you may want to check other NP-Complete problems as well. One such list.

Edit 1:

AliVar made a good point. The given problem searches for Y > X and the knapsack problem searches for Y < X. So the answer for this problem needs a few more steps. When we are trying to find the minimum sum where Y > X we are also looking for the maximum sum where S < (Total - X). The second part is the original knapsack problem. So;

1. Find the total
2. Solve knapsack for S < (Total - X)
3. Subtrack the list of items in knapsack solution from the original input.
4. This should give you the minimum Y > X

Answer 2

Let A be our array. Here is a O(X*N) algorithm:

initialize set S = {0}
initialize map<int, int> parent
best_sum = inf
best_parent = -1
for a in A
     Sn = {}
     for s in S
         t = s + a
         if t > X and t < best_sum
             best_sum = t
             best_parent = s
         end if
         if t <= X
             Sn.add(t)
             parent[t] = s
         end if
     end for
     S = S unite with Sn
end for

To print the elements in the best sum print the numbers:

Subarray = {best_sum - best_parent}
t = best_parent
while t in parent.keys()
    Subarray.add(t-parent[t])
    t = parent[t]
end while
print Subarray

The idea is similar to the idea of dynamic programming. We just calculate all reachable (those that could be obtained as a subarray sum) sums that are less than X. For each element a in the array A you could either choose to participate in the sum or not. At the update step S = S unite with Sn S represent all sums in which a does not participate while Sn all sum in which a do participate.

You could represent S as a boolean array setting a item true if this item is in the set. Note that the length of this boolean array would be at most X.

Overall, the algorithm is O(X*N) with memory usage O(X).