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?
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.
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;
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).
p? I assumed it is the same as parent, but when I try to print the elements, it does not work. However, your algorithm does give the correct best_sum (verified by brute-force).
p should be parent. It should be fine. I will try to test it.parent, now it all works.I think this problem is NP-hard and the subset sum can be reduced to it. Here is my reduction: For an instance of the subset sum with set S={x1,...,xn} it is desired to find a subset with sum t. Suppose d is the minimum distance between two non-equal xi and xj. Build S'={x1+d/n,...,xn+d/n} and feed it to your problem. Suppose that your problem found an answer; i.e. a subset D' of S' with sum Y>t which is the smallest sum with this property. Name the set of original members of D' as D. Three cases may happen: 1) Y = t + |D|*d/n which means D is the solution to the original subset sum problem. 2) Y > t + |D|*d/n which means no answer set can be found for the original problem. 3) Y < t + |D|*d/n. In this case assign t=Y and repeat the problem. Since the value for the new t is increased, this case will not repeat exponentially. Therefore, the procedure terminates in polynomial time.
O(X*Y)acceptable?