我必须找到号码差最低的总和。

I have to find the lowest possible sum from numbers' difference.

让我们说我有4个数字。 1515，1520，1500和1535的区别的最低金额为30，因为1535年至1520年= 15安培;＆安培; 1515至1500年= 15和15 + 15 = 30。如果我会做这样的：1520至15年= 5安培;＆安培; 1535 - 1500 = 35这将是40之

Let's say I have 4 numbers. 1515, 1520, 1500 and 1535. The lowest sum of difference is 30, because 1535 - 1520 = 15 && 1515 - 1500 = 15 and 15 + 15 = 30. If I would do like this: 1520 - 1515 = 5 && 1535 - 1500 = 35 it would be 40 in sum.

希望你得到它，如果没有，问我。

Hope you got it, if not, ask me.

任何想法如何计划呢？我刚刚发现这个网上，试图从我的语言为英语翻译。这听起来很有趣。我不能这样做暴力破解，因为它会采取不同年龄的编译。我不需要code，只是想法如何编程或code小片段。

Any ideas how to program this? I just found this online, tried to translate from my language to English. It sounds interesting. I can't do bruteforce, because it would take ages to compile. I don't need code, just ideas how to program or little fragment of code.

感谢。

编辑： 我没有张贴一切...还有一个版本：

I didn't post everything... One more edition:

我已经让我们说8种可能的数字。但我只有6个采取使最小的总和。例如，数字 1731，1572，2041，1561，1682，1572，1609，1731 ，最小的总和将是48，但在这里我必须从只需要6个号码8。

I have let's say 8 possible numbers. But I have to take only 6 of them to make the smallest sum. For instance, numbers 1731, 1572, 2041, 1561, 1682, 1572, 1609, 1731, the smallest sum will be 48, but here I have to take only 6 numbers from 8.

推荐答案

的solution通过marcog 是正确的，非递归，多项式时间解决问题的方法 - 这是一个pretty的标准DP的问题 - 但是，只是为了完整性，这里有一个证明，它的工作原理，以及实际的code代表的问题。 [@marcog：随意，如果你希望的任何部分这个答案复制到你自己的;然后我会删除。]

The solution by marcog is a correct, non-recursive, polynomial-time solution to the problem — it's a pretty standard DP problem — but, just for completeness, here's a proof that it works, and actual code for the problem. [@marcog: Feel free to copy any part of this answer into your own if you wish; I'll then delete this.]

让列表为x 1 ，...，X N 。假设wlog该列表进行排序。我们正试图找到K（不相交），对从列表中的元素，使得他们之间的分歧和达到最小。

Let the list be x1, …, xN. Assume wlog that the list is sorted. We're trying to find K (disjoint) pairs of elements from the list, such that the sum of their differences is minimised.

要求：最佳的解决方案总是由连续元素的差异。 证明：假设你修复元件，其差异采取的子集。然后由proof乔纳斯Kölker给出，只是这个子集的最优解的 的包括在列表连续元素的差异。现在假设有对应于不包含对连续元素的子集的溶液，即溶液涉及差X Ĵ -x 我其中j> i + 1的。然后，我们可以替换x Ĵ为x I + 1 得到一个更小的差异，因为 x 我≤x I + 1 ≤x Ĵ⇒x I + 1 -x 我≤x Ĵ -x 我。 （不用说，如果x I + 1 = X Ĵ，然后进行X I + 1 是进行X Ĵ区分）。这证明了这一说法。

Claim: An optimal solution always consists of the differences of consecutive elements. Proof: Suppose you fix the subset of elements whose differences are taken. Then by the proof given by Jonas Kölker, the optimal solution for just this subset consists of differences of consecutive elements from the list. Now suppose there is a solution corresponding to a subset that does not comprise pairs of consecutive elements, i.e. the solution involves a difference xj-xi where j>i+1. Then, we can replace xj with xi+1 to get a smaller difference, since xi ≤ xi+1 ≤ xj ⇒ xi+1-xi ≤ xj-xi. (Needless to say, if xi+1=xj, then taking xi+1 is indistinguishable from taking xj.) This proves the claim.

剩下的只是常规动态规划的东西：用k对从第n个元素无论是最佳的解决方案根本不使用的第n个元素（在这种情况下，它只是最佳用k对从第一个正解1）， 或的它使用的第n个元素在这种情况下，它的差X N -x N-1 加使用最佳溶液从第一n-2 k-1个双

The rest is just routine dynamic programming stuff: the optimal solution using k pairs from the first n elements either doesn't use the nth element at all (in which case it's just the optimal solution using k pairs from the first n-1), or it uses the nth element in which case it's the difference xn-xn-1 plus the optimal solution using k-1 pairs from the first n-2.

整个程序的时间为O（N日志N + NK），作为marcog说。 （分选+ DP）

The whole program runs in time O(N log N + NK), as marcog says. (Sorting + DP.)

下面是一个完整的计划。我是懒惰与初始化数组和使用类型的字典写的Python code;这是在用实际阵列小日志（N）的因素。

Here's a complete program. I was lazy with initializing arrays and wrote Python code using dicts; this is a small log(N) factor over using actual arrays.

'''
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