文档章节

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

李勇2
 李勇2
发布于 2015/03/02 09:38
字数 304
阅读 13
收藏 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
BZOJ 1143 祭祀river【二分图之偏序集的最大反链】

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

Anxdada
2017/11/30
0
0
[BZOJ1237][SCOI2008]配对(贪心+dp)

版权声明:本文为博主原创文章,转载请附上原博客链接。 https://blog.csdn.net/CABI_ZGX/article/details/82917742 传送门 题意:n 个整数A[i]和n个整数B[i]。把它们配对,要求所有配对的整...

_Mocha_
10/01
0
0

没有更多内容

加载失败,请刷新页面

加载更多

ES5和ES6那些你必须知道的事儿

  ES5和ES6那些你必须知道的事儿      ES5新增的东西      一、数组方法      1、forEach      用途:遍历,循环      对于空数组不会执行回调函数      复制代码...

SEOwhywhy
25分钟前
2
0
转:[windows]DOS批处理添加任务计划

[windows]DOS批处理添加任务计划 博客分类: Windows 转自:http://gwmold.blog.163.com/blog/static/1553319892010117113457232/ 自动创建每周运行一次的计划任务 创建计划任务可用at,sch...

SamXIAO
30分钟前
3
0
redis 问题总结

1:修改内存页大小,linux 默认大小是4k(通过getconf PAGE_SIZE 查看 2:查看内存交换信息,防止使用内存交换 3: sar -n DEV 查看网络状况 4: 修改文件句柄: ulimit -n 65535 5: info memo...

昏鸦
32分钟前
2
0
如何在Rails应用程序中使用Kafka?

背景介绍 有那么一段时间,我们的系统需要用到分布式流式处理和消息系统,而 Apache Kafka 似乎成了我们建立业务关键型应用程序的坚实基础。它可用于很多场景下,比如产品更新管道、订单跟踪...

java菜分享
33分钟前
2
0
C#匿名委托

list自定义排序 //list自定义排序public static List<string> sortList(List<string> m_str,string splitStr) //a b表示列表中的元素{String[] strArray=m_str.ToArray();......

青衣霓裳
43分钟前
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部