CODEWITHSUNDEEP
pythonalgorithm
Zanatos
Zanatos

Reputation: 91

Maximum non-contiguous sum of values in list less than or equal to k

I have a list of values [6,1,1,5,2] and a value k = 10. I want to find the maximum sum of values from the list that is less than or equal to k, return the value and the numbers used. In this case the output would be: 10, [6,1,1,2].

I was using this code from GeeksForGeeks as an example but it doesn't work correctly (in this case, the code's result is 9).

The values do not need to be contiguous - they can be in any order.

def maxsum(arr, n, sum):
    curr_sum = arr[0]
    max_sum = 0
    start = 0;

    for i in range(1, n):
        if (curr_sum <= sum):
            max_sum = max(max_sum, curr_sum)

        while (curr_sum + arr[i] > sum and start < i):
            curr_sum -= arr[start]  
            start += 1

        curr_sum += arr[i]  

    if (curr_sum <= sum): 
        max_sum = max(max_sum, curr_sum)  

    return max_sum 

if __name__ == '__main__': 
    arr = [6, 1, 1, 5, 2]  
    n = len(arr)  
    sum = 10

print(maxsum(arr, n, sum))

I also haven't figured out how to output the values that are used for the sum as a list.

Upvotes: 0

Views: 898

Answers (2)

schwartz721
schwartz721

Reputation: 1027

Here's a solution using itertools.combinations. It's fast enough for small lists, but slows down significantly if you have a large sum and large list of values.

from itertools import combinations

def find_combo(values, k):
    for num_sum in range(k, 0, -1):
        for quant in range(1, len(values) + 1):
            for combo in combinations(values, quant):
                if sum(combo) == num_sum:
                    return combo

values = [6, 1, 1, 5, 2]
k = 10
answer = find_combo(values, k)
print(answer, sum(answer))

This solution works for any values in a list and any k, as long as the number of values needed in the solution sum doesn't become large.

The solution presented by user10987432 has a flaw that this function avoids, which is that it always accepts values that keep the sum below k. With that solution, the values are ordered from largest to smallest and then iterated through and added to the solution if it doesn't bring the sum higher than k. However a simple example shows this to be inaccurate:
values = [7, 5, 4, 1] k = 10
In that solution, the sum would begin at 0, then go up to 7 with the first item, and finish at 8 after reaching the last index. The correct solution, however, is 5 + 4 + 1 = 10.

Upvotes: 0

kaya3
kaya3

Reputation: 51037

This problem is at least as hard as the well-studied subset sum problem, which is NP-complete. In particular, any algorithm which solves your problem can be used to solve the subset sum problem, by finding the maximum sum <= k and then outputting True if the sum equals k, or False if the sum is less than k.

This means your problem is NP-hard, and there is no known algorithm which solves it in polynomial time. Your algorithm's running time is linear in the length of the input array, so it cannot correctly solve the problem, and no similar algorithm can correctly solve the problem.

One approach that can work is a backtracking search - for each element, try including it in the sum, then backtrack and try not including it in the sum. This will take exponential time in the length of the input array.

If your array elements are always integers, another option is dynamic programming; there is a standard dynamic programming algorithm which solves the integer subset sum problem in pseudopolynomial time, which could easily be adapted to solve your form of the problem.

Upvotes: 2

Related Questions