c - 三爪分区(动态编程示例)

Question

我有一个 int 数组，其中包含像 {47, 94, 79, 90, 89, 14, 82, 92} 这样的数字。该数组必须分为三个子数组，以便每个数组的总和尽可能小，也就是最小。我认为它值得使用递归来解决，但是这种方法使我逃脱了，我还想过在初始数组上使用 qsort 然后“贪婪地”划分它，但它并不总是有效(例如采取最低和最高数字等)。

例如上面的数字将分为:
1) {94, 90, 14}
2) {92, 89}
3) {82, 79, 47}

这里第三个数组包含最高的最小和，即 208。数字的顺序无关紧要。问题是如何将数字公平地分成三组，使它们形成最小的总和。我必须测试所有可能性吗？

Answer 1

可以使用动态规划对所描述的问题进行建模。我们可以定义一个状态空间如下。

v[i,t1,t2] := minimal load in partition 3 attainable for items
              in {0,...,i} where the total load in partition 1
              is exactly t1 and the total load in t2 is exactly t2
              if such a load exists and positive infinity otherwise

对于状态空间，i在{0,...n}，而t1,t2 位于 {0,...,P} 中，其中 P 是项目的总和，它是目标值的上限，并且由n*smax 其中 smax 是输入中出现的最大值。

我们得到以下递归关系，其中情况基本上取决于迭代选择每个元素分配到哪个分区，其中 s_i 表示 i 的大小- 第一项。

v[i,t1,t2] = min { v[i-1,t1-s_i,t2],
                   v[i-1,t1,t2-s_i],
                   v[i-1,t1,t2] + s_i }

最小表达式中的第一项对应于将项目 i 分配到分区 3，第二种情况对应于将项目 i 分配到分区 2，第三种情况对应将项目i分配给分区3。状态空间填充后，可以通过计算以下表达式获得所需的结果(即分区的最小最大负载)。

Result = min { max { t1, t2, v[n,t1,t2] : t1, t2 in {0,...,P} } }

在上面的最大值表达式中，t1对应分区1的负载，t2对应分区2的负载，状态值 v[n,t1,t2] 对应于分区 3 中的负载。草图算法的运行时间可以由 O(n^3*smax)，这是一个伪多项式运行时界限。如果还需要将项目最佳分配到分区中，则必须使用回溯或辅助数据结构。

请注意，给其中一个相同的分区赋予特殊角色似乎是人为的，因为它的负载是状态值，而其他分区的负载用于状态空间的轴。此外，乍一看，状态的值似乎很容易获得，因为它只是剩余的总负载

sum_{j=1}^{i} s_i - ( t1 + t2 )

但事实并非如此，因为上述数量只确定分区 3 中的负载，如果这样的分配确实存在的话；在状态空间的定义中，使用正无穷表示不存在这样的赋值。

该方法与描述的方法非常相似 here , 第 12 页 ff。总的来说，所描述的问题可以看作是一个调度问题，即最小化 3 个相同的并行机器的完工时间。在所谓的three-field notation ，这个问题被表示为P3||Cmax，这意味着机器的数量不是输入的一部分，而是固定的。