2

Given an array of positive integers and an upper limit MAX, i have to find the sub-sequence with sum <= MAX. There can be many sub-sequences whose sum is <= MAX .
We have to find that one with max sum possible.

  • I am not looking for the exponential-time solution. The array can have upto 1-2k elements and MAXX can be very large, upto 10^9 or something.

  • Neither am i looking for the 0,1-knapsack approach. It works in O(N^2) and i have to call this method around 1-2k times.

Can we do it any better?

Futher I would like to add I'm not looking for an algorithm that gives 100% accurate answers. I am trying to achieve a golden-mean between time-complexity and accuracy.
Any Ideas?

The more accurate the better. By this what I mean, I explain here below.

When ever a subset is found, it is removed from the total set.
The Next subset is formed from the remaining elements.

Suppose the subset formed sums to Y

As per the question Y should be <=MAX. Now lets take the difference of MAXX and Y,

X = MAXX - Y

AND we add it up to TOTAL i.e. we do for each each subset

TOTAL+=Y

We have to minimize X as much as we can.

Is there a way in which we can take advantage of the the following fact?

the remaining set is the total set minus the subset formed

Hope this explains the question.

Dhruv Chandhok
  • 780
  • 7
  • 18

2 Answers2

2

Well I explain my approach here so that others may improve upon the following algorithm.

Concepts Required - A.V.L. Tree (AVL tree is a hieght-balanced BST)

Algorithm:-

For all elements in A
{
 if(A[i]=MAX) add to the subsets.
 if(A[i]>MAX) skip the element, Its not part of any subset.
 if(A[i]<MAX) insert in AVL Tree
} 
REMAINING <-- MAX
CURRENT_SET <-- NULL
     while(TREE IS NOT EMPTY)
     {
            TEMP <-- Maximum element in tree which is less than REMAINING (Using Search in AVL Tree)
            if(TEMP IS NULL)
            {
                CURRENT_SET is added to the set of subsets
            }
            else
            {
                REMAINING <-- REMAINING - TEMP
                CURRENT_SET <-- CURRENT_SET + TEMP 
                Delete TEMP from the AVL TREE
            }
     }
Dhruv Chandhok
  • 780
  • 7
  • 18
0

well you can find the all the possible subsequence in array (How to determine the longest increasing subsequence using dynamic programming? ) whose sum is less than or equal to MAX and then you can sort all these sum obtained and then accordingly you can find the sum which is just less than or equal to MAX. If you want the sequence then again use this new sum and check for sub sequence which sums upto that sum.

You can use some optimization also 1. whenever you find some sum = MAX return the answer directly. 2. you don't need to sort the list of sums obtained ( not sure about this but i think the result would be in sorted order, You can see it yourself).

Overall complexity will be O(nlogn).

Community
  • 1
  • 1
aurilio
  • 102
  • 6
  • I dont think the complexity is O(n log n). You said " find the all the possible subsequence in array (dynamic programming solution) whose sum is less than or equal to MAX" . Which method are you reffering to and what is its complexity? – Dhruv Chandhok Apr 09 '14 at 09:39
  • My bad Dynamic Programming will take O(n^2) although i have found a O(nlogn) solution http://en.wikipedia.org/wiki/Longest_increasing_subsequence#Efficient_algorithms you can see this. – aurilio Apr 09 '14 at 09:47
  • http://stackoverflow.com/questions/2631726/how-to-determine-the-longest-increasing-subsequence-using-dynamic-programming just have a look at this solution link – aurilio Apr 09 '14 at 09:49
  • I guess that is altogether a different problem. It is LIS- Longest Increasing Subsequence.How do you relate the two? – Dhruv Chandhok Apr 09 '14 at 10:00
  • Well you can use the logic to find different subsequence sum, that's why i suggested it. – aurilio Apr 09 '14 at 10:32
  • But It will only find those subsequence which are increasing in nature. It would not even consider subsequences like 4 2 3. Suppose Our array is 5 4 4 2 3. Then our answer should be (5,4) and (4,2,3). But It would not consider any of these. It would give (5) , (4,4) and (2,3). – Dhruv Chandhok Apr 09 '14 at 10:43
  • And your AVL solution is different from what your question is, and do explain what you are trying to achieve with it. – aurilio Apr 09 '14 at 10:44
  • well you want contiguous sequence or what ? it's not clear. You mean something like this http://en.wikipedia.org/wiki/Subset_sum_problem – aurilio Apr 09 '14 at 10:48
  • No I do not want contigous sequence, I mentioned It's a subsequence not a sub-array. – Dhruv Chandhok Apr 09 '14 at 10:58
  • You can first sort your list and them perform DP until subset with sum in interval [MAX-threshold, MAX] appears. – Alex Salauyou Apr 09 '14 at 16:28
  • Well it's more like subset sum problem which can be solved in O(n*MAX) time, you can use that logic and built solution array on it and after that with the help of a loop you can check in array for existence of solution. – aurilio Apr 10 '14 at 09:35