CODEWITHSUNDEEP
c++arraysalgorithmdynamic-programming
S13 k
S13 k

Reputation: 9

Subsequence having sum at most 'k'

Given a non decreasing array A of size n and an integer k, how to find a subsequence S of the array A with maximum possible sum of its elements, such that this sum is at most k. If there are multiple such subsequences, we are interested in finding only one.

For example, let the array be {1, 2, 2, 4} so, n = 4 and let k = 7. Then, the answer should be {1, 2, 4}.

Brute force approach takes approximately O(n(2^n-1)) but is there a more efficient solution to this problem?

Upvotes: 0

Views: 761

Answers (1)

SaiBot
SaiBot

Reputation: 3745

In the general case the answer is no.

Just deciding if there is a solution where elements sum up to k is equivalent to the Subset Sum Problem and thus already NP-complete.

The Subset Sum Problem can be equivalently formulated as: given the integers or natural numbers w_1,... ,w_n does any subset of them sum to precisely W

However, if either n or the number of bits P that it takes to represent the largest number w is small there might be more efficient solution (e.g., a pseudo-polynomial solution based on dynamic programming if P is small). Additionally, if all your numbers w are positive then it might also be possible to find a better solution.

Upvotes: 1

Related Questions