总和大于 python 中值的最小子集

Question

给定不同维度列表的列表，最快的方法是什么，找到总和大于或等于特定值的所有最小子集？

所以如果集合和值是

A = [[1],[1,2,3,4],[5,6],[10],[1000,12],[11]]
value = 10

解决方案是

res = [[10],[11]]

或再次：

A = [[1,10],[1,2,3,4],[5,6],[10,10],[1000,12,1],[1,10,11]]
value = 10
res = [[1,10],[10,10]]

提前致谢

Answer 1

您可以使用以下 python 代码：该代码在 A 中找到长度列表然后按升序检查子列表，即大小为 1 的子列表，然后是大小 2，然后是大小 4。请注意，如果结果中已包含较小的子列表，则代码不会检查较大的子列表。

A = [[1],[1,2,3,4],[5,6],[10],[1000,12],[11]]
value = 10

lens = list(set([len(i) for i in A]))   #result = [1,2,4]
res = []
for l in lens:
    if len(res) == 0: 
        for i in A: 
            if len(i) == l: 
                if sum(i) >= value: 
                    res.append(i)
print(res)   #result = [[10], [11]]

Answer 2

这就是我在 (2^nd) 评论中所说的内容。使用简单的列表理解找出所有满足条件的子列表：

>>> lists = [[1], [1, 2, 3, 4], [5, 6], [10], [1000, 12], [11]]
>>> value = 10
>>>
>>> [l for l in lists if sum(l) >= value]
[[1, 2, 3, 4], [5, 6], [10], [1000, 12], [11]]

所以，我们有一些可以工作但可能被认为很慢的东西（好吧，不是这个特定的例子，但对于更大的输入列表）。它是慢，因为它搜索所有满足条件的子列表，而实际上只有 length 1 的子列表（在这种情况下）应该被尝试。

我想到的第 1^st 件事是根据长度对输入列表中的子列表进行排序。但是排序本身也可能很慢，实际上我们只需要将它们分组即可。一种方法是使用字典，其中键是子列表的长度，对于特定键，值是包含具有该长度的所有子列表的列表：

>>> d = {}
>>> for l in lists:
...     d.setdefault(len(l), []).append(l)
...
>>> d
{1: [[1], [10], [11]], 4: [[1, 2, 3, 4]], 2: [[5, 6], [1000, 12]]}
>>>
>>> ret = []
>>>
>>> for i in sorted(d):  # Traverse the (sorted) lengths
...     for l in d[i]:
...         if sum(l) >= value:
...             ret.append(l)
...     if ret:  # Once a specific length was handled, if there are some results, simply stop
...         break
...
>>>
>>> ret
[[10], [11]]

或者，作为函数：

def filter_sublists(sublists, min_sum_threshold):
    d = {}
    for l in sublists:
        d.setdefault(len(l), []).append(l)
    ret = []
    for i in sorted(d):
        for l in d[i]:
            if sum(l) >= min_sum_threshold:
                ret.append(l)
        if ret:
            break
    return ret

总和大于 python 中值的最小子集

smallest subsets with sum larger than value in python

python

sum

sublist