python - 组合列表列表以获得项目组 <= 但尽可能接近长度 X 的最有效方法

Question

假设我有一个列表列表，例如:

 [ [ a1, a2, a3, a4, a5], [b1, b2, b3, b4, b5, b6, b7, b8], [c1, c2, c3, c4, c5, c6], [d1, d2, d3, d4] ]

比较所有列表项长度并将它们组合成长度尽可能接近但小于或等于 x 的列表的列表的最简单方法是什么？

所以对于上面的例子，x=12:

[ [a1, a2, a3, a4, a5, c1, c2, c3, c4, c5, c6], [b1, b2, b3, b4, b5, b6, b7, b8, d1, d2, d3, d4] ]

输出中各个组(例如 a、b、c...)的顺序并不重要，但不能拆分各个组。

我知道我可以，例如，获取第一组的长度，然后按顺序获取每个后续​​组的长度，如果它们的总和 = x 则弹出这些列表并将它们的项目附加到返回的列表中，如果然后不再遍历每个组，检查它们的长度之和是否=x-1，如果是，则弹出并追加，然后使用长度之和=x-2 等，直到输入列表为空。

对于像给定的例子这样的小团体，这会很好地工作，但是当输入列表的 len 变得非常大时呢？有没有更高效的方法/算法？

Answer 1

看来是装箱问题。

我的 greedy algorithm with swapping and pre-sorting应该可以，但是您需要使子列表长度适应图片高度，并根据您的 x 和项目的总长度计算初始 bin 计数。