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.

Answer 1

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)]