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

Question

我有一个值(整数)列表，我想将其拆分为 B 个非空子列表，而不更改其初始顺序。目标是调整文本的大小以使其适合定义的区域。

每个子列表都有一个与其关联的指标:其值的总和。我想最小化所有子列表中最大总和与最小总和之间的差异DIFF。这将使我能够将文本分成文本量大致相同的行。

编辑

正如所建议的，它也可以最小化最大总和，因为这会导致最小化一行文本的最大长度。

示例:

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

解:L1 = {2,3,4} 且 L2 = {5,6}。总和 (L1) = 9、总和 (L2) = 11 和 DIFF = 2

---

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

解:L1 = {1,1,8}，L2 = {1,1,1} 且 L3 = {8,1}。Sum(L1) = 10，Sum(L2) = 3，Sum(L3) ) = 9 且 DIFF = 7

我的建议

由于我没有 IT 背景，所以我不知道如何解决这个问题。 首先，我尝试计算出可以将原始集合拆分为 B 子列表的组合数量。 原始列表中的元素数量为N，那么可能的拆分数量等于:

然后我尝试看看什么是找到全局最小值的合适算法。我认为，如果我遇到满足以下两个条件的情况，我就会达到全局最小值。

• 将元素从(一个)最大的子列表移动到(一个)其邻居中并不会改善DIFF。
• 将元素从(一个)最小的子列表移动到(一个)其邻居中并不会改善DIFF。

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

问题

提到的两个条件是否足以保证全局最小值(对于 DIFF)？

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

您有什么阅读建议可以帮助我解决此类问题吗？

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

谢谢!

Answer 1

问:提到的两个条件是否足以保证全局最小值(对于 DIFF)？

答:不

考虑以下列表:{6,5,2,4,3,7} with 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

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