从一个n个数的数组中选择P个独立的对，使对的绝对差值之和最小

Question

存在一个包含n个正整数的数组。必须从数组中选择p对独立的对，使得对的绝对差之和最小。n> = 2 * P。我一直在思考这个算法，但无法想出一个解决问题的办法。n = 7, p = 2
A = [a1, a2, a3, a4, a5, a6, a7]
假设一人选择两对(a1, a3)和(a4, a6)。
S = abs(a1-a2) + abs(a1- a6)。
与选择的任何其他对相比，这些对的最小值应为S，如果它们是答案。

我想的是我需要首先对数组进行排序，并且不知何故我需要应用DP，但无法获得递归。

有人能帮忙吗?

Answer 1

在排序表上的动态规划状态可以是:设dp[i][k]表示对k对索引i的最佳配对，其中sorted_list[i]是对中较大的成员。然后:

dp[0][_] = Infinity
dp[i][1] = sorted_list[i] - sorted_list[i-1]
dp[i][k] = min(dp[i-1][k], sorted_list[i] - sorted_list[i-1] + dp[i-2][k-1])
where 0 < k ≤ ceil(i / 2)