我想弄清楚在这种情况下我应该如何使用福特富尔克森算法这种情况有点像数独.我们有一个a包含整数值的矩阵.每列的最后一列和每列的最后一行包含整个行/列的总和.
例:
int[][] a = {{1, 3, 5, 9},
{4, 2, 1, 7},
{5, 5, 6, *}} // * Is not determined since the sums
// * do not count as summable values.
这就是矩阵中的值并不总是正确的.总和的值并不总是正确的,例如:
int[][] a = {{1, 3, 3, 9},
{2, 3, 1, 7},
{5, 5, 6, *}} // * Is not determined since the sums do
// * not count as summable values.
有一个矩阵b,其中包含一个单元格可以满足给定总和的最大差异.例如
int[][] b = {{1, 0, 3},
{2, 1, 2}}
例如,对于值 …
假设我们有一系列整数:a = {2,4,3,5}
我们有k = 3.
我们可以在k(3)子数组中拆分数组a,其中数组的顺序不能改变.每个子阵列的总和必须尽可能低,以便所有子阵列中的最大总和尽可能低.
对于上述解决方案,这将给出{2,4},{3},{5},其最大总和为6(4 + 2).
一个错误的回答将是{2},{4,3},{5},因为最大总和是7在此情况下(4 + 3).
我已经尝试创建一个贪婪的算法,它通过对所有整数求和并将其除以子阵列的结果量来计算整个阵列的平均值.所以在上面的例子中,这意味着14/3 = 4(整数除法).然后它会将数字加到计数器上,只要它<平均数.然后它将重新计算子阵列的其余部分.
我的解决方案给出了一个很好的近似值,可以用作启发式算法,但并不总能给出正确的答案.
有人可以帮我解决一个算法,它为我提供了所有情况的最佳解决方案,并且优于O(N²)？我正在寻找一个大约为O(n log n)的算法.
提前致谢!