文档章节

证明两个集合的划分最小绝对值差问题

liyong2
 liyong2
发布于 2015/03/02 09:38
字数 304
阅读 20
收藏 0
c

#程序员薪资揭榜#你做程序员几年了?月薪多少?发量还在么?>>>

总的 解空间的大小 是

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 的情况的约束条件




本文转载自:http://blog.csdn.net/liyong748/article/details/7559882

liyong2

liyong2

粉丝 54
博文 203
码字总数 66584
作品 0
广州
程序员
私信 提问
加载中

评论(0)

如何用整数规划求解NP完全问题

如何用整数规划求解NP完全问题 一、NP完全问题 NP完全问题是一类具有非常高难度的组合最优化问题, 所有NP完全问题都是NP难问题。虽然P问题是比较容易的问题, NP问题却不一定是困难问题,必...

osc_vnse1t2o
2019/11/12
2
0
P2762 太空飞行计划问题(网络流24题之一)

题目描述 W 教授正在为国家航天中心计划一系列的太空飞行。每次太空飞行可进行一系列商业性实验而获取利润。现已确定了一个可供选择的实验集合E={E1,E2,…,Em},和进行这些实验需要使用的...

osc_imfpapvz
2018/01/09
2
0
LeetCode.1200-最小绝对值差(Minimum Absolute Difference)

这是小川的第418次更新,第451篇原创 看题和准备 今天介绍的是LeetCode算法题中Easy级别的第268题(顺位题号是1200)。给定一个由不同的整数组成的数组,找到所有对元素,其中任意两个元素的...

程序员小川
2019/10/06
0
0
文本相似度计算基本方法小结

相似度计算方面 Jaccard相似度:集合之间的Jaccard相似度等于交集大小与并集大小的比例。适合的应用包括文档文本相似度以及顾客购物习惯的相似度计算等。 Shingling:k-shingle是指文档中连续...

小萝卜_
2016/05/24
301
1
leetcode 1049 Last Stone Weight II(最后一块石头的重量 II)

思路:原问题可以转换为将数组分割为两个集合(根据符号为正和符号为负划分),使得这两个集合和的差最小。可以等价为01背包问题。那么dp[i][j]就是将前i个物品放到容量为j的背包能得到的最大值...

osc_s5ssp1ty
2019/05/20
2
0

没有更多内容

加载失败,请刷新页面

加载更多

好的可视化编辑器收集

国内 https://www.ivx.cn/index 国外 https://vectr.com

lilugirl
35分钟前
15
0
怎么在分享流程图的时候设置密码?迅捷画图教你保密小技巧!

怎么在分享流程图的时候设置密码?相信大家对分享链接和密码已经不陌生了,毕竟现在分享资源主要用的网盘、网站等等,基本上都需要先获取密码,才能进入分享链接页面,从分享资源的角度来说,...

赛利亚大姐大
35分钟前
13
0
如何在Mac电脑中输入多种标点符号和文字表情

特殊的标点符号和表情怎么输入?MAC电脑有自己自带的输入法,但是对于一些表情符号很多人都不知道在哪里使用,现在就来介绍一下MAC如何输入多种标点符号和文字表情。 1、首先我们打开备忘录,...

mac小叮当
45分钟前
17
0
Ubuntu替换国内源

网络环境的原因,官方的apt的源的速度比较慢,打算替换为国内源,正好学校有Ubuntu的源,所以替换下 编辑文件/etc/apt/sources.list 将其中的内容换为对应的系统的目标源即可。 选择你的ubu...

zhangwenwen
今天
14
0
持续交付的最后一英里

如果开发人员的变更集在集成时并没有实现长期部署就绪的状态,那么你的团队其实就没有真正的实践持续交付。 想要完全优化产品开发周期,你需要在团队中强调无缝部署的重要性,使每位工程师都...

京东智联云开发者
今天
18
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部