文档章节

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

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

粉丝 45
博文 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
轻松入门机器学习之概念总结(一)

欢迎大家前往腾讯云社区,获取更多腾讯海量技术实践干货哦~ 作者:许敏 前言 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
拔河比赛---C语言代码,编译器Xcode

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

都英俊兮
2016/06/17
614
7

没有更多内容

加载失败,请刷新页面

加载更多

下一页

php 使用redis锁限制并发访问类

1.并发访问限制问题 对于一些需要限制同一个用户并发访问的场景,如果用户并发请求多次,而服务器处理没有加锁限制,用户则可以多次请求成功。 例如换领优惠券,如果用户同一时间并发提交换领...

豆花饭烧土豆
17分钟前
0
0
Linux环境搭建 | 手把手教你配置Linux虚拟机

在上一节 「手把你教你安装Linux虚拟机」 里,我们已经安装好了Linux虚拟机,在这一节里,我们将配置安装好的Linux虚拟机,使其达到可以开发的程度。 Ubuntu刚安装完毕之后,还无法进行开发,...

良许Linux
18分钟前
0
0
Nginix开启SSL支持HTTPS访问(自签名方法)

Nginix开启SSL支持HTTPS访问(自签名方法) 超文本传输安全协议(缩写:HTTPS,英语:Hypertext Transfer Protocol Secure)是超文本传输协议和SSL/TLS的组合,用以提供加密通讯及对网络服务器...

openthings
35分钟前
0
0
(三)Nginx配置·续

概述 前文写了关于Nginx环境配置,但是还没有完,接下来将会继续讲三个相关的配置 主要是以下三个 1.Nginx访问日志 2.Nginx日志切割 3.静态文件不记录日志和过期时间 Nginx访问日志 1.先看看...

杉下
今天
1
0
jquery创建类似于java的map

var map = {}; // Map map = new HashMap(); map[key] = value; // map.put(key, value); var value = map[key]; // Object value = map.get(key); var has = key in map; // boolean has = ......

SuperDabai
今天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部