pul*_*asa 8 language-agnostic algorithm recurrence
我需要一些帮助来找到算法的一般想法来解决以下问题.在任务中给了我这个问题.看起来它应该可以通过贪婪的方法解决,但我无法找到一个简单的解决方案.这是问题描述:
现在给你的序列ñ号a_1 ... a_n这样0 = a_1 < a_2 < ... < a_n.您必须消除这些数字中的至多 M个,以使a_i+1 - a_i任何两个连续数字之间的最小差异 最大化.
你可能不会消除第一个和最后一个元素,a_0和a_n.此外,你必须消除尽可能少的数字:如果消除M - 1你得到最短的距离D并消除M你仍然有相同的最小差异,你不能消除这最后一个数字.
我不是要求这个问题的完整解决方案.关于算法的外观,只有一些指导.
编辑:一些测试样本.请记住,可能有多个有效的解决方案.
Remove at most 7 from:
0 3 7 10 15 18 26 31 38 44 53 60 61 73 76 80 81 88 93 100
Solution:
0 7 15 26 31 38 44 53 60 73 80 88 93 100
Remove at most 8 from:
0 3 7 10 15 26 38 44 53 61 76 80 88 93 100
Solution:
0 15 38 53 76 88 100
[编辑:我最初声称ElKamina的答案是错误的,但我现在已经确信自己不仅是正确的,它与我(后面)的答案几乎相同:-P虽然我的口味仍然有点简洁!]
这是一个精确的O(NM ^ 2)时间,O(NM)空间 动态编程算法,它以毫秒为单位得到所有OP示例的正确答案.基本思路是:
在下文中,x [i]表示列表中的第i个数字,索引从0开始.
令f(i,j)是从位置0 <= i <N开始的数字列表的后缀可获得的最佳(最大最小)间隔大小,通过保持该(即第i个)数并且精确地删除后者的j(不一定是连续的)数字.以下递归显示了如何计算:
f(i, j) = max(g(i, j, d)) over all 0 <= d <= min(j, N-i-2)
g(i, j, d) = min(x[i+d+1] - x[i], f(i+d+1, j-d))
该min(j, N-i-2)有而不是只是普通的J即可防止删除"过去的结束".我们需要的唯一基础案例是:
f(N-1, 0) = infinity (this has the effect of making min(f(N-1), 0), z) = z)
f(N-1, j > 0) = 0 (this case only arises if M > N - 2)
更详细地,为了计算f(i,j),我们所做的是循环遍历从位置i + 1开始的连续删除的所有可能数(包括零),在每种情况下计算(a)由(a)形成的间隔的最小值.这个删除块和(b)子块问题的最佳解决方案,从该块右侧第一个未删除的数字开始. 以指定在一个块中的第一数量(X [1])没有被删除是很重要的,从而使一(父)子问题的间隔总是"封端". 这是一个棘手的部分,花了我一段时间才弄明白.
如果您对上面的普通递归进行编码,它将起作用,但是在M和N中需要时间指数.通过记忆 f(),我们保证它的主体将运行最多N*M次(每个不同的参数组合一次) .每次运行该函数时,它会执行O(M)工作扫描,通过越来越长的删除块,整个O(NM ^ 2)时间.
您不能通过使用较少的删除来创建更大的间隙,因此可以通过查看M + 1结果f(0,M),f(0,M-1),...,f来找到总体最大最小间隔大小(0,0)的第一数目比以前的许多较小的:以前的数是答案,并且所述第二参数f()是需要删除的最小数目.要找到最佳解决方案(即删除的特定数字列表),您可以记录在单独的前任数组中做出的决策,以便p [i,j]给出d的值(可以将其转换为先前的值i和j)导致f(i,j)的最优解.(也许"前任"在这里令人困惑:它指的是在当前子问题之前解决的子问题,尽管这些子问题出现在代表当前子问题的后缀"之后"(右侧).)然后可以遵循这些链接恢复删除/不删除决定.
有了这样一个棘手的问题,看看错误的方法并确切地看出它们出错的位置会很有帮助......:/ /我以为我已经解决了问题,但我没有注意到要求返回解决方案使用尽可能少的删除,我最初尝试解决这个问题不起作用.
首先,我尝试将f(i,j)定义为从位置0 <= i <N开始的数字列表的后缀可获得的最佳(最大最小)间隔大小,保持此(即第i个)数字并删除任何地方从0到j的后来(不一定是连续的)数字.但是这引起了一个微妙的问题:从最佳解决方案到子问题,你不一定能够组合出最优解决方案.我最初认为这可以通过更改函数来修复,以返回(间隔大小,实现该间隔大小所需的最小删除次数)对而不仅仅是间隔大小,并使其在共享最大最小间隔的操作之间断开关系通过始终选择最小化删除次数的操作来确定大小.但这一般情况并非如此,因为子问题的最佳解决方案(即数字列表的某些后缀)将花费删除使得该区域中的最小间隔大小尽可能大,即使这些删除变得浪费因为完整解决方案的前缀无论如何都会迫使总体最小值降低.这是一个使用f()返回的反例(间隔大小,实现该大小所需的最小删除次数)对:
Problem: M = 1, X = [10 15 50 55].
f(2, 0) = (5, 0) (leaving [50 55])
f(1, 1) = (40, 1) (delete 50 to leave [15 55]); *locally* this appears better
than not deleting anything, which would leave [15 50 55] and yield
a min-gap of 5, even though the latter would be a better choice for
the overall problem)
f(0, 1) = max(min(5, f(1, 1)), min(40, f(2, 0))
= max(min(5, 40), min(40, 5))
= (5, 1) (leaving either [10 15 55] or [10 50 55])
我没有显示f(0,1)返回的对的第二个元素的工作,因为它很难简洁地表达,但显然它将是1,因为两个替代方案都需要1个删除.