文档章节

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

李勇2
 李勇2
发布于 2015/03/02 09:38
字数 304
阅读 12
收藏 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

共有 人打赏支持
李勇2

李勇2

粉丝 46
博文 189
码字总数 62209
作品 0
广州
程序员
文本相似度计算基本方法小结

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

小萝卜_
2016/05/24
96
1
ccf-2017-12-1-最小差值

原题: 问题描述 试题分析:最先想到的就是将数存放到数组中,2层循环计算最小差值绝对值即可。(考试的时候智商不在线不知道怎么写的,没有得满分) AC代码: #include include using names...

Big_laoshu
02/02
0
0
拔河比赛---C语言代码,编译器Xcode

拔河比赛规矩把所有人分成A B两队,力气大的一方胜出由于一开始不知道每个人力量多大,所以主持人分组定下如下策略:根据每个人的体重尽可能的分配平均分配的策略是: A B两队人数相差 <= 1 A...

都英俊兮
2016/06/17
614
7
轻松入门机器学习之概念总结(一)

欢迎大家前往腾讯云社区,获取更多腾讯海量技术实践干货哦~ 作者:许敏 前言 1,机器学习算法分类 1)监督学习: 有train set,train set里面y的取值已知。 2)无监督学习:有train set, tr...

云加社区
2017/12/15
0
0
BZOJ 1143 祭祀river【二分图之偏序集的最大反链】

传送门 //题意: 就是给定一个有向无环图, 选择尽量多的点使得其中任意的两个点都不能相互到达. //思路: 在有向无环图中,有如下的一些定义和性质: 链:一条链是一些点的集合,链上任意两个点...

Anxdada
2017/11/30
0
0

没有更多内容

加载失败,请刷新页面

加载更多

网站优化技术包括哪些内容

网站优化Incapsula超越简单的内容缓存,可以优化网站性能或应用程序的用户体验,优化包括内容缩小、动态文件压缩、图像压缩、会话重用优化、TCP优化和连接预合并。 动态文件压缩,普通的web...

上树的熊
19分钟前
1
0
业界 | Teradata全球调研:四分之三企业分析项目数据科学家“缺货”

当地时间10月15日,2018 Teradata全球用户大会在美国拉斯维加斯举行。来自15个国家的3000多位数据人参与了本次峰会。 大会第一日,Teradata发布了针对“企业数据分析”的2018年调研结果。 调...

Mr_zebra
21分钟前
1
0
java 通过Unsafe不使用构造器直接创建对象

这里有一个User没有无参构造 public class User { static { System.out.println("static {}"); } { System.out.println("{}"); } public User(Strin......

ValSong
22分钟前
1
0
eureka 高可用配置 unavailable-replicas 问题.

在使用spring cloud 配置eureka 高可用配置时.发现配置的节点一直无法获取心跳. eureka控制台界面上一直显示的挂载节点 是 unavailable-replicas 查看日志.就是获取心跳的地址不对. 默认的健...

拖鞋莫止步
23分钟前
1
0
Vue2 模板template的四种写法

<div id="app">    <h1>我是直接写在构造器里的模板1</h1></div> <template id="demo3">    <h1 style="color:red">我是选项模板3</h1></template> <script type="x-t......

粒子数反转
23分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部