文档章节

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

李勇2
 李勇2
发布于 2015/03/02 09:38
字数 304
阅读 10
收藏 0
点赞 0
评论 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
博文 188
码字总数 62209
作品 0
广州
程序员
文本相似度计算基本方法小结

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

小萝卜_ ⋅ 2016/05/24 ⋅ 1

ccf-2017-12-1-最小差值

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

Big_laoshu ⋅ 02/02 ⋅ 0

BZOJ 1143 祭祀river【二分图之偏序集的最大反链】

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

Anxdada ⋅ 2017/11/30 ⋅ 0

轻松入门机器学习之概念总结(一)

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

云加社区 ⋅ 2017/12/15 ⋅ 0

拔河比赛---C语言代码,编译器Xcode

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

都英俊兮 ⋅ 2016/06/17 ⋅ 7

背包问题 (knapsack problem)

0/1背包问题: 某种限制下的最优问题。整体最优可以由部分最优得到。 由于子问题相交,可以用动态规划方法求解。即,利用空间记录中间计算结果,后续的计算通过简单的判断和查表得到。 中间结...

ChenQi ⋅ 2012/05/21 ⋅ 0

第K顺序统计量的求解

一个n个元素组成的集合中,第K个顺序统计量(Order Statistic)指的是该集合中第K小的元素,我们要讨论的是如何在线性时间(linear time)里找出一个数组的第K个顺序统计量。 一、问题描述 ...

songlee ⋅ 2014/06/22 ⋅ 0

数据挖掘 自习笔记 第二章 数据处理实践(上)

数据清洗中噪声数据处理 (1)Bin 方法 :通过利用相应被平滑数据点的周围点,对一组排序数据进行平滑。 如:有价格数据。 首先对价格数据进行排序,然后将其划分成若干高度的bin(即每个bin...

urge104 ⋅ 2013/04/14 ⋅ 1

Leetcode 220. Contains Duplicate III

Given an array of integers, find out whether there are two distinct indices i and j in the array such that the absolute difference between nums[i] and nums[j] is at most t and t......

ShutLove ⋅ 2017/11/29 ⋅ 0

Codeforces Round #467 (Div. 1) E:Iqea(点分治)

传送门 题解: 把每列的不同联通块看做一个点,相邻列若有共同的纵坐标有格子那么连边,这样会形成一棵树,且网格上两点的路径就是树上的一条路径。 然后就是点分治裸题,不过算距离比较麻烦...

qq_35649707 ⋅ 03/05 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

行政区划代码转为字典形式

原数据为: http://www.mca.gov.cn/article/sj/xzqh/2018/201804-12/201804-06041553.html 手动替换了一下格式,并使用下面的代码处理. # 输入格式s = """110000:北京市110101:东城区1101...

漫步海边小路 ⋅ 19分钟前 ⋅ 0

android apk 签名

创建key,需要用到keytool.exe (位于C:\Program Files\Java\jdk1.6.0_10\bin目录下),使用产生的key对apk签名用到的是jarsigner.exe (位于C:\Program Files\Java\jdk1.6.0_10\bin目录下),把...

国仔饼 ⋅ 28分钟前 ⋅ 0

springcloud+jps+mybatis多数据库配置

多数据库配置 配置我们目录结构设置: config ---datasource ----jpa ----mybatis ----redis Datasource中是数据的相关配置 Jap中是springDatajpa的相关配置 Mybatis中是mybatis的相关配置 ...

大-智-若-愚 ⋅ 35分钟前 ⋅ 0

Spring mvc HandlerMapping 实现机制

概述 当DispatcherServlet接受到客户端的请求后,SpringMVC 通过 HandlerMapping 找到请求的Controller。 HandlerMapping 在这里起到路由的作用,负责找到请求的Controller。 Spring MVC 默认...

轨迹_ ⋅ 39分钟前 ⋅ 0

JavaScript零基础入门——(十)JavaScript的DOM基础

JavaScript零基础入门——(十)JavaScript的DOM基础 欢迎大家回到我们的JavaScript零基础入门,上一节课,我们了解了JavaScript中的函数,这一节课,我们来了解一下JavaScript的DOM。 第一节...

JandenMa ⋅ 今天 ⋅ 0

Weex起步

本教程假设你已经在你的本地环境安装了node 其实weex起步教程在 https://github.com/lilugirl/incubator-weex 项目说明文件中都已经有了,但为了有些同学看到英文秒变文盲,所以这里我重新写...

lilugirl ⋅ 今天 ⋅ 0

Jenkins实践1 之安装

1 下载 http://mirrors.jenkins.io/war/latest/jenkins.war 2 启动 java -jar jenkins.war 前提:安装jdk并配置环境变量 启动结果节选: ************************************************......

晨猫 ⋅ 今天 ⋅ 0

组合数学 1-2000 中,能被6或10整除的数的个数

1--2000 中,能被6或10整除的数的个数 利用集合的性质 能被6整除的个数 2000/6 = 333 能被10整除的个数 2000/10 = 200 能被6和10整除的个数 2000/30 = 66 能被6或10整除的个数 333+200-66 =...

阿豪boy ⋅ 今天 ⋅ 0

一篇文章学懂Shell脚本

Shell脚本,就是利用Shell的命令解释的功能,对一个纯文本的文件进行解析,然后执行这些功能,也可以说Shell脚本就是一系列命令的集合。 Shell可以直接使用在win/Unix/Linux上面,并且可以调用...

Jake_xun ⋅ 今天 ⋅ 0

大数据工程师需要精通算法吗,要达到一个什么程度呢?

机器学习是人工智能的一个重要分支,而机器学习下最重要的就是算法,本文讲述归纳了入门级的几个机器学习算法,加大数据学习群:716581014一起加入AI技术大本营。 1、监督学习算法 这个算法由...

董黎明 ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部