Algorithm to find the longest combination who's sum is less than or equal to a value

Question

I have a list of tuples (the actual list can be very big), the first element in the tuple indicates the index, and the second indicates the value. I also have a number n:

lst = [(0,1), (1,2), (2,4), (3,5), (4,1), (5,2)]
n = 6

I want to find the largest combination that will give me the sum of values which is less than or equal to n. So in this example the answer should be a list like the following:

[(0,1), (1,2), (4,1), (5,2)]

because 1+2+1+2 = 6 is the largest combination of values in lst that yields a sum which is less or equal to n.

I need to find something that works on lists with, say, 200-300 elements at least.

alani · Accepted Answer · 2020-09-04 16:03:49Z

2

Using a copy of the list sorted in order of increasing value, accumulate tuples until the total would exceed the target, and then sort back into index order.

lst = [(0,1), (1,2), (2,4), (3,5), (4,1), (5,2)]
n = 6

total = 0
answer = []
for tup in sorted(lst, key=lambda t:t[1]):
    val = tup[1]
    if total + val > n:
        break
    answer.append(tup)
    total += val

answer.sort(key=lambda t:t[0])
    
print(answer)

Gives:

[(0, 1), (1, 2), (4, 1), (5, 2)]

answered Sep 4, 2020 at 16:03

alani

13.2k3 gold badges18 silver badges34 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Thierry Lathuille · Accepted Answer · 2020-09-04 16:01:12Z

1

Start by sorting the tuples by value, then take as many as you can while staying under the limit:

from operator import itemgetter

lst = [(0,1), (1,2), (2,4), (3,5), (4,1), (5,2)]
n = 6

sorted_list = sorted(lst, key=itemgetter(1))

out = []
total = 0

for index, value in sorted_list:
    total += value
    if total <= n:
        out.append((index, value))
    else:
        break
        
print(out)
# [(0, 1), (4, 1), (1, 2), (5, 2)]

answered Sep 4, 2020 at 16:01

Thierry Lathuille

24.4k10 gold badges50 silver badges57 bronze badges

Comments

ponylama · Accepted Answer · 2020-09-04 16:19:47Z

0

lst = [(0,1), (1,2), (2,4), (3,5), (4,1), (5,2)]

n = 5

sorted_lst_second_element = sorted(lst, key=lambda x: x[1])

sum = 0
max_sum_list = []
for i in range (len(lst) - 1):
    sum = sum + sorted_lst_second_element[i][1]
    if sum<=n:
        max_sum_list.append(sorted_lst_second_element[i])
    else:
        break

print(sorted_lst_second_element)
print(max_sum_list)

answered Sep 4, 2020 at 16:19

ponylama

513 bronze badges

Collectives™ on Stack Overflow

Algorithm to find the longest combination who's sum is less than or equal to a value

3 Answers 3

Comments

Comments

Comments

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Related