证明两个集合的划分最小绝对值差问题
博客专区 > 李勇2 的博客 > 博客详情
证明两个集合的划分最小绝对值差问题
李勇2 发表于3年前
证明两个集合的划分最小绝对值差问题
  • 发表于 3年前
  • 阅读 9
  • 收藏 0
  • 点赞 0
  • 评论 0

腾讯云 技术升级10大核心产品年终让利>>>   

总的 解空间的大小 是

C(2n, n)/2  =  2n!/(n!*n!)/2

从2n个元素中取出n个元素的组合数目,  又由于对称性 , 所以除以2

例如: 1234 ---》 取出两个元素的组合:  12  13 14 23 24 34

分成两个集合的可能性是: (12, 34), (13, 24), (14, 23)

生成组合的程序:

n = 4
p = range(0, n)
def get(seq, k):
    m = len(seq)
    print m, k
    if k == 0:
        return [[]]
    if m < k:
        return []
    res = []
    for i in get(seq[1:], k-1):
        res.append([seq[0]]+i)
    res += get(seq[1:], k)
    return res
r = get(p, n/2)
print r

当n=1 时候:唯一的解

当n=2时候: 可以元素按照 从小到大排序,  a1 <= a2 <= a3<= a4

那么最优解决是: (a1,a4 )  (a2,a3)

证明如下:

(a1, a2) (a3, a4) 组合 的差值的绝对值最大, 因为对于任意的 2n个元素中取出n个元素,头n个元素之和最小, 最后n个元素之和最大, 差值绝对值自然最大

又有如下

(a1, a3), (a2, a4) |a1-a2+a3-a4| = |a1-a2|+|a3-a4| >= |a1+a4-(a2+a3)|

所以(a1,a4), (a2,a3) 组合解最优


证明n=3 的情况的约束条件




标签: c
共有 人打赏支持
李勇2
粉丝 43
博文 183
码字总数 60421
×
李勇2
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: