算法：通过最小化所有子列表之间元素和的最大差异，将值列表分离为子集

Question

我有一个值（整数）的列表，我想拆分成B非空子列表，而不改变它们的初始顺序。目标是调整文本的大小，使其适合定义的区域。

每个子列表将有一个与之关联的指标：其值的总和。我想最小化所有子列表中最大和和最小和之间的差异DIFF。这将允许我将文本分成几乎相同数量的文本行。

编辑

正如所建议的那样，它还可以最小化最大和，因为这将导致最小化文本行的最大长度。

示例：

给定列表L={2,3,4,5,6}和B=2。

解决方案：L1={2,3,4}和L2={5,6}。和（L1）=9，和（L2）=11，差=2

给定列表L={1,1,8,1,1,1,8,1}和B=3

解：L1={1,1,8}，L2={1,1,1}和L3={8,1}。和（L1）=10，和（L2）=3，和（L3）=9和DIFF=7

我的建议

由于我没有信息技术背景，我不知道如何处理这个问题。首先，我试图计算出我可以将原始集合分割成B子列表的组合数量。原始列表中的元素数量为N，那么可能存在的分裂数量等于：

然后我试着看看什么是找到全局最小值的合适算法。我想，如果我遇到了以下两个条件都得到尊重的情况，我就会达到全球最小值。

• 将一个元素从（一个）最大的子列表移动到（一个）相邻的子列表中并不会改善差异。

（由于子列表不能为空，从只有一个元素的子列表中移动一个元素需要更改多个子列表）

问题

上述两个条件是否足以保证全局最小值（对于差异）？

你知道/记得解决这个问题的算法吗？或者你有解决这个的建议吗？

你有什么阅读建议来帮助我解决这类问题吗？

正如我所说，我没有It背景，也没有太多处理此类计算机理论问题的经验。

非常感谢。

Answer 1

问：上述两个条件是否足以保证全局最小值（对于差异）？

A：没有

考虑下面的列表：<代码> {6，5，2，4，3，7}，B＝3 < /代码>

以及以下可能的解决方案：

{6} {5,2,4} {3,7};  Sums=(6,11,10),  DIFF = 11-6 = 5

所有来自最大组的单元素更改都会使DIFF变得更糟，或者保持不变：

{6,5} {2,4} {3,7};  Sums=(6,11,10),  DIFF = 11-6 = 5
{6} {5,2} {4,3,7};  Sums=(6,7,14),  DIFF = 14-6 = 8
{6} {5,2,4,3} {7};  Sums=(6,14,7),  DIFF = 14-6 = 8

但有一个更好的解决方案：

{6,5} {2,4,3} {7};  Sums=(11,9,7),  DIFF = 11-7 = 5

所以你的方法只找到局部极小值，而不是全局极小值。