我有两个间隔序列.
第一个是固定的和不重叠的,所以类似于:
[1..10], [12..15], [23..56], [72..89], ...
第二个不是固定的,所以它只是间隔长度的有序列表:
[7, 2, 5, 26, ...]
手头的任务是:
很简单的例子:
[25..26], [58..68], [74..76], [78..86]
[10, 12]
最佳解决方案是将长度10的间隔设置为[58..68],将长度12的间隔设置为[74..86],这样只会将数字25,26和77放在一个列表中但不是其他.
我提出的唯一一个似乎有点帮助的是,如果我按顺序放下间隔,我知道我已经创建的间隔有多少'惩罚',所以我有一个分数的上限,意味着我有一个可接受的启发式算法,我可以进行A*搜索而不是查看整个树.但是,总的数字范围从0到34M左右,所以我想要更好的东西.
任何帮助都会很热!
好的，这是一个经过深思熟虑的答案。它应该在多项式时间内工作，但我没有费心检查索引是什么。很可能获得比此处概述的答案更好的索引。详细信息留给读者作为练习:-) 我希望它不会太不清楚。
我将解决方案的分数定义为出现在两个间隔列表中的整数的数量。令 f(i,m) 为仅使用前 i 个间隔长度即可获得的最高分数，前提是您的间隔均不超过 m。对于固定 i，函数 f 本质上是一个从整数到整数有界子集的（非严格）递增函数。所以：
这意味着可以使用有限数据结构来表示 f(i,m) 的所有值（仍然考虑 i 的固定值）。
现在令 F(i) 为该数据结构的值，表示 f(i,m) 的所有值。我声称，给定 F(i)，可以计算 F(i+1)。为此，我们只需要对所有 x 回答以下问题：如果我将新的区间放在 x 处，我能得到的最佳解决方案有多好？但我们知道这是什么 - 它只是 f(i,x) + 我们从这个区间得到的分数。
因此，如果 n 是第二个列表中的间隔数，则最佳解决方案的得分将为 F(n)。
要真正找到解决方案，您可以从这里向后推算。
你知道你能得到的最好成绩是多少。假设它是 s_0。然后将最后一个区间放在尽可能靠左的位置，前提是它可以让你得分 s_0。即找到最小的 m 使得 f(n,m) = s_0; 并将间隔放置在 m 处的边界内。
然后，让 s_1 为您需要从所有其他间隔获得的分数，以便获得总计 s_0。将倒数第二个间隔放置在尽可能靠左的位置，前提是您仍然可以得分 s_1。即找到最小的 m 使得 f(n,m) = s_1; 并将间隔放置在 m 处的边界内。
等等...