Subset sum Algorithm with modification

Question

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.

Are the entries allowed to be negative? Does the subarray have to be contiguous? — David Mahone
No there are no negative enteries and no it does not have to be contigous. Sorry, its a subsequence not a subarray. — Dhruv Chandhok
This is an unclear question. If you have no objective way of evaluating a solution, then it is impossible to provide a useful answer. — nneonneo

Dhruv Chandhok Dhruv Chandhok · Accepted Answer · 2014-04-09T10:26:04

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
            }
     }

Subset sum Algorithm with modification

2 Answers