查找总和小于或等于某个值的最长组合的算法

Question

我有一个元组列表（实际列表可能很大），元组中的第一个元素表示索引，第二个元素表示值。我还有一个号码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 个元素的列表的内容。

Answer 1

首先按值对元组进行排序，然后在不超过限制的情况下尽可能多地取用：

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

Answer 2

使用按值递增顺序排序的列表副本，累积元组直到总数超过目标，然后按索引顺序排序。

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

Answer 3

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)

查找总和小于或等于某个值的最长组合的算法

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

python

computer-science

python-3.x