Largest Subset whose sum is less than equal to a given sum

Question

A list is defined as follows: [1, 2, 3]

and the sub-lists of this are:

[1], [2], [3],  
[1,2]  
[1,3]
[2,3]  
[1,2,3]

Given K for example 3 the task is to find the largest length of sublist with sum of elements is less than equal to k.

I am aware of itertools in python but it will result in segmentation fault for larger lists. Is there any other efficient algorithm to achieve this? Any help would be appreciated.

My code is as allows:

from itertools import combinations
def  maxLength(a, k):
#print a,k
l= []

i = len(a)
while(i>=0):
    lst= list(combinations(sorted(a),i))
    for j in lst:
        #rint list(j)
        lst = list(j)
        #print sum(lst)
        sum1=0
        sum1 = sum(lst)
        if sum1<=k:
            return len(lst)
    i=i-1

Answer 1

Look, for generating the power-set it takes O(2^n) time. It's pretty bad. You can instead use the dynamic programming approach.

Check in here for the algorithm. http://www.geeksforgeeks.org/dynamic-programming-subset-sum-problem/

And yes, https://www.youtube.com/watch?v=s6FhG--P7z0 (Tushar explains everything well) :D

Answer 2

As far as I can see (since you treat sub array as any items of the initial array) you can use greedy algorithm with O(N*log(N)) complexity (you have to sort the array):

1. Assign entire array to the sub array
2. If sum(sub array) <= k then stop and return sub array
3. Remove maximim item from the sub array
4. goto 2

Example

[1, 2, 3, 5, 10, 25] 
 k = 12

Solution

sub array = [1, 2, 3, 5, 10, 25], sum = 46  > 12, remove 25
sub array = [1, 2, 3, 5, 10],     sum = 21  > 12, remove 10
sub array = [1, 2, 3, 5],         sum = 11 <= 12, stop and return       

As an alternative you can start with an empty sub array and add up items from minimum to maximum while sum is less or equal then k:

sub array = [],               sum =  0 <= 12, add 1
sub array = [1],              sum =  1 <= 12, add 2          
sub array = [1, 2],           sum =  3 <= 12, add 3             
sub array = [1, 2, 3],        sum =  6 <= 12, add 5             
sub array = [1, 2, 3, 5],     sum = 11 <= 12, add 10             
sub array = [1, 2, 3, 5, 10], sum = 21 >  12, stop, 
                              return prior one: [1, 2, 3, 5]           

Answer 3

You can use the dynamic programming solution that @Apy linked to. Here's a Python example:

def largest_subset(items, k):
    res = 0

    # We can form subset with value 0 from empty set,
    # items[0], items[0...1], items[0...2]
    arr = [[True] * (len(items) + 1)]

    for i in range(1, k + 1):
        # Subset with value i can't be formed from empty set
        cur = [False] * (len(items) + 1)

        for j, val in enumerate(items, 1):
            # cur[j] is True if we can form a set with value of i from
            # items[0...j-1]
            # There are two possibilities
            # - Set can be formed already without even considering item[j-1]
            # - There is a subset with value i - val formed from items[0...j-2]
            cur[j] = cur[j-1] or ((i >= val) and arr[i-val][j-1])
        if cur[-1]:
            # If subset with value of i can be formed store
            # it as current result
            res = i

        arr.append(cur)
    return res

ITEMS = [5, 4, 1]
for i in range(sum(ITEMS) + 1):
    print('{} -> {}'.format(i, largest_subset(ITEMS, i)))

Output:

0 -> 0
1 -> 1
2 -> 1
3 -> 1
4 -> 4
5 -> 5
6 -> 6
7 -> 6
8 -> 6
9 -> 9
10 -> 10

In above arr[i][j] is True if set with value of i can be chosen from items[0...j-1]. Naturally arr[0] contains only True values since empty set can be chosen. Similarly for all the successive rows the first cell is False since there can't be empty set with non-zero value.

For rest of the cells there are two options:

1. If there already is a subset with value of i even without considering item[j-1] the value is True
2. If there is a subset with value of i - items[j - 1] then we can add item to it and have a subset with value of i.

Answer 4

Assume everything is positive. (Handling negatives is a simple extension of this and is left to the reader as an exercise). There exists an O(n) algorithm for the described problem. Using the O(n) median select, we partition the array based on the median. We find the sum of the left side. If that is greater than k, then we cannot take all elements, we must thus recur on the left half to try to take a smaller set. Otherwise, we subtract the sum of the left half from k, then we recur on the right half to see how many more elements we can take.

Partitioning the array based on median select and recurring on only 1 of the halves yields a runtime of n+n/2 +n/4 +n/8.. which geometrically sums up to O(n).