从数字的差异中获得尽可能低的总和

Question

我必须从数字的差异中找到最低的总和.

假设我有4个数字.1515,1520,1500和1535.差异的最小值是30,因为1535 - 1520 = 15 && 1515 - 1500 = 15和15 + 15 = 30.如果我愿意这样做:1520 - 1515 = 5 && 1535 - 1500 = 35总计40.

希望你明白,如果没有,请问我.

任何想法如何编程？我刚刚在网上找到这个,试图从我的语言翻译成英语.听起来很有趣.我不能做暴力,因为编译需要很长时间.我不需要代码,只是想法如何编程或代码的一小部分.

谢谢.

编辑: 我没有发布所有内容......还有一个版本:

我让我们说8个可能的数字.但我必须只拿其中的6个来赚取最小的金额.例如,数字1731, 1572, 2041, 1561, 1682, 1572, 1609, 1731,最小的总和将是48,但在这里我只需要从8个数字中取6个数字.

Answer 1

考虑编辑:

首先对列表进行排序.然后使用动态编程解决方案,当仅考虑序列中的前i个数时,状态i,n表示n个差的最小和.初始状态:dp [*] [0] = 0,其他一切=无穷大.使用两个循环:外部循环遍历i从1到N,内部循环循环通过n从0到R(在编辑的示例情况下为3 - 这使用3对数字,这意味着6个单独的数字).你的递归关系是dp [i] [n] = min(dp [i-1] [n],dp [i-2] [n-1] + seq [i] - seq [i-1]).

你必须要注意处理我忽略的边界情况,但是一般的想法应该工作并且将在O(N log N + NR)中运行并使用O(NR)空间.

Answer 2

marcog的解决方案是一个正确的,非递归的,多项式时间解决问题的方法 - 这是一个非常标准的DP问题 - 但是,为了完整性,这里有一个证据证明它有效,以及问题的实际代码.[@marcog:如果你愿意,可以随意将这个答案的任何部分复制到你自己的; 我会删除它.]

证明

让列表为x ₁,...,X _ñ.假设列表已排序的wlog.我们试图从列表中找到K(不相交)元素对,以便最小化它们之间的差异总和.

声明:最优解决方案总是由连续元素的差异组成.
证明:假设您修复了差异所在的元素子集.然后通过JonasKölker给出的证明,该子集的最优解决方案包括列表中连续元素的差异.现在假设存在对应于不包括连续元素对的子集的解,即该解涉及差x _j -x _i,其中j> i + 1.然后,我们可以替换x _Ĵ为x _{I + 1}得到一个更小的区别,因为
X _我 ≤X _{I + 1} ≤X _Ĵ⇒X _{i + 1的} -x _我 ≤X _Ĵ -x _我.
(不用说,如果x _{i + 1} = x _j,则取x _{i + 1}与x _j无法区分.)这证明了这一说法.

其余的只是常规的动态编程:使用前n个元素中的k对的最优解决方案根本不使用第n个元素(在这种情况下,它只是使用来自第一个n-1的k对的最优解),或者它使用第n个元素,在这种情况下,它是差x _n -x _n-1加上使用来自第一个n-2的k-1对的最优解.

marcog说,整个程序及时运行O(N log N + NK).(排序+ DP.)

码

这是一个完整的计划.我很懒,初始化数组并使用dicts编写Python代码; 这是使用实际数组的小log(N)因子.

'''
The minimum possible sum|x_i - x_j| using K pairs (2K numbers) from N numbers
'''
import sys
def ints(): return [int(s) for s in sys.stdin.readline().split()]

N, K = ints()
num = sorted(ints())

best = {} #best[(k,n)] = minimum sum using k pairs out of 0 to n
def b(k,n):
    if best.has_key((k,n)): return best[(k,n)]
    if k==0: return 0
    return float('inf')

for n in range(1,N):
    for k in range(1,K+1):
        best[(k,n)] = min([b(k,n-1),                      #Not using num[n]
                           b(k-1,n-2) + num[n]-num[n-1]]) #Using num[n]

print best[(K,N-1)]

测试一下:

Input
4 2
1515 1520 1500 1535
Output
30

Input
8 3
1731 1572 2041 1561 1682 1572 1609 1731
Output
48

Answer 3

我假设一般问题是:给定2n个整数的列表,输出n对的列表,使得| x - y |的总和 在所有对(x,y)上尽可能小.

在这种情况下,想法是:

• 排序数字
• 发出(numbers[2k], numbers[2k+1])的k = 0, ..., n - 1.

这有效.证明:

假设你有x_1 < x_2 < x_3 < x_4(可能在它们之间有其他值)和输出(x_1, x_3)和(x_2, x_4).然后

|x_4 - x_2| + |x_3 - x_1| = |x_4 - x_3| + |x_3 - x_2| + |x_3 - x_2| + |x_2 - x_1| >= |x_4 - x_3| + |x_2 - x_1|.

换句话说,它总是更好的输出(x_1, x_2),并(x_3, x_4)因为你不冗余覆盖之间的空间x_2和x_3的两倍.通过归纳,2n的最小数量必须与第二个最小数量配对; 通过对列表的其余部分进行归纳,将最小邻居配对总是最优的,因此我提出的算法草图是正确的.

Answer 4

订购清单,然后进行差异计算.

编辑:嗨@hey

您可以使用动态编程解决问题.

假设你有一个列表L的N整数,你必须形成k对(与2*k <= N)

构建一个函数,找到列表中的最小差异(如果列表已排序,则会更快;)调用它 smallest(list l)

构建另一个为两对找到相同的(可能很棘手,但可行)并调用它 smallest2(list l)

让我们定义best(int i, list l)一个函数,为i列表中的对提供最佳结果l

算法如下:

1. 最好的(1,L)=最小(L)
2. 最好的(2,L)=最小2(L)
3. 我从1到k:

环

compute min ( 
    stored_best(i-2) - smallest2( stored_remainder(i-2) ),
    stored_best(i-1) - smallest( stored_remainder(i-1) 
) and store as best(i)
store the remainder as well for the chosen solution

现在,问题是一旦你选择了一对,形成边界的两个整数被保留,不能用于形成更好的解决方案.但是通过查看两个级别,您可以保证您已经允许切换候选人.

(切换工作由完成smallest2)