将键值对划分为 n 组总和为 y 或更小的算法

Algorithm to divide key value pairs into n groups of sum y or smaller

提问人：Daniel Smith 提问时间：7/6/2020 更新时间：7/6/2020 访问量：44

问：

我有一个这样的键值对：

'NANOUSDT.csv.gz': 15,
'ENJUSDT.csv.gz': 19,
'DGBBTC.csv.gz': 0,
'BTSUSDT.csv.gz': 1,
'BLZBTC.csv.gz': 42,
'BANDUSDT.csv.gz': 14,
'ETCUSDT.csv.gz': 202

它包含大约 300 多个项目。有些很大。有些很小。我想创建一个具有以下条件的密钥列表列表：

  1. 列表中的值之和不能超过 10,000
  2. 一个列表不能包含超过 8 个元素

没有一件商品的尺寸超过 10,000。

我怎样才能做到这一点？

与 Python 语言无关

评论

0赞 Balaji Ambresh 7/6/2020
这是作业问题吗？
0赞 Daniel Smith 7/6/2020
不。我正在尝试在多线程中处理多个文件。我需要打开文件并处理。打开时我不能超过我的 CPU 内核/RAM。10000 是我的 RAM 限制的占位符，8 是我的处理器内核限制的占位符。以为这也是一个有趣的问题。
0赞 Martial P 7/6/2020
参见 Knapsack 问题，这是一个 NP 完备问题。您可以找到许多高性能算法，这些算法可以产生高效的组合。“最佳”组合需要与所有其他组合进行比较，但组合的数量（复杂度）是阶乘的（n！

答：

0赞 Balaji Ambresh 7/6/2020 #1

下面是一个示例：

kvs = {'1': 9999,
       '2': 19,
       '3': 0,
       '4': 1,
       '5': 42,
       '6': 14,
       '7': 14,
       '8': 14,
       '9': 14,
       '10': 14,
       '11': 10000}
buckets = []
cur_bucket = []
weight_so_far = 0
for k, v in kvs.items():
    if len(cur_bucket) == 8 or weight_so_far + v > 10000:
        buckets.append(cur_bucket)
        cur_bucket = []
        weight_so_far = 0
    weight_so_far += v
    cur_bucket.append(k)
if cur_bucket:
    buckets.append(cur_bucket)

print(buckets)

输出

[['1'], ['2', '3', '4', '5', '6', '7', '8', '9'], ['10'], ['11']]

这是你要找的吗？

评论

0赞 Daniel Smith 7/6/2020
是的。但是，如果这些团体更聪明，我更喜欢它。我所说的聪明是指，拥有尽可能少的组数。在您的示例中，如果 [1,3,4] 位于同一组中，则如果字典较大，则组数可能会更小。
0赞 Balaji Ambresh 7/6/2020
@DanielSmith 在这种情况下，此问题是装箱的实例。
0赞 Daniel Smith 7/6/2020
谢谢。事实正是如此。

上一个：轴旋转

下一个：在间隔不均匀的时间序列中检测峰值