Блог

У меня есть список кортежей (фактический список может быть очень большим), первый элемент в кортеже указывает индекс, а второй указывает значение. У меня также есть число n :

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

Я хочу найти самую большую комбинацию, которая даст мне сумму значений, которая меньше или равна n . Итак, в этом примере ответом должен быть список, подобный следующему:

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

потому что 1 2 1 2 = 6 это самая большая комбинация значений в lst , которая дает сумму, которая меньше или равна n .

Мне нужно найти что-то, что работает со списками, скажем, с 200-300 элементами, по крайней мере.

Используя копию списка, отсортированного в порядке возрастания значения, накапливайте кортежи до тех пор, пока общая сумма не превысит целевую, а затем отсортируйте обратно в порядке индекса.

 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)
  

Дает:

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

Начните с сортировки кортежей по значению, затем возьмите столько, сколько сможете, оставаясь при этом ниже предела:

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

 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)