| 网站首页 | 业界新闻 | 小组 | 交易 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
共有 626 人关注过本帖
标题:第二个用数学思想来写程序的小探索过程记录
只看楼主 加入收藏
zhu224039
Rank: 8Rank: 8
等 级:贵宾
威 望:17
帖 子:862
专家分:792
注 册:2012-7-29
结帖率:59.52%
  已结贴   问题点数:20  回复次数:5   
第二个用数学思想来写程序的小探索过程记录
2006 年百度之星程序设计大赛初赛题目 5

座位调整

题目描述:

百度办公区里到处摆放着各种各样的零食。百度人力资源部的调研发现,员工如果可以在自己喜欢的美食旁边工作,工作效率会大大提高。因此,百度决定进行一次员工座位的大调整。

调整的方法如下:

1 . 首先将办公区按照各种零食的摆放分成 N 个不同的区域。(例如:可乐区,饼干区,牛奶区等等)。

2 . 每个员工对不同的零食区域有不同的喜好程度(喜好程度度的范围为 1 — 100 的整数, 喜好程度越大表示该员工越希望被调整到相应的零食区域)。

3 . 由于每个零食区域可以容纳的员工数量有限,人力资源部希望找到一个最优的调整方案令到总的喜好程度最大。

数据输入:

第一行包含两个整数 N , M ,( 1<=N , M<=300 )。分别表示 N 个区域和 M 个员工。

第二行是 N 个整数构成的数列 a ,其中 a[i] 表示第 i 个区域可以容纳的员工数, (1<=a[i]<=M , a[1]+a[2]+..+a[N]=M) 。

紧接着是一个 M*N 的矩阵 P , P ( i , j )表示第 i 个员工对第 j 个区域的喜好度。

答案输出:

对于每个测试数据,输出可以达到的最大的喜好程度。

输入样例


3 3

1 1 1

100 50 25

100 50 25

100 50 25


输出样例


175

[ 本帖最后由 zhu224039 于 2014-6-30 05:07 编辑 ]
搜索更多相关主题的帖子: 美食 可乐 办公区 百度 程序设计 
2014-06-30 03:00
zhu224039
Rank: 8Rank: 8
等 级:贵宾
威 望:17
帖 子:862
专家分:792
注 册:2012-7-29
  得分:0 
由题目: N 个整数构成的数列 a ,其中 a[i] 表示第 i 个区域可以容纳的员工数, (1<=a[i]<=M , a[1]+a[2]+..+a[N]=M) 。
得知结论:  M>=N
喜好度和区间的关系
喜好度可相同:
对一个区间有多个喜好度 都相同的情况
区间存在包容性:
一个区间能够容忍喜好度相同的人的个数
在区间具有包容的情况下,是有竞争度存在的,也就是说  一个区间没有包容完喜好度相同的人,还有一部分人心存不满 ,凭什么你进得我进不得,也许我更合适


按照贪心算法来说,可以这样来组织人员的安排

不考虑竞争的情况下:(何谓竞争:在同一个区间有多个喜好度一样的人存在,且区间包容不完)
当(M〉N 且N区间都没满)
先从M个人中取出N个人来放入N个区间,按尽可能的安排喜好度最大的进去,形成安排第一批人的 喜好度最大解 f(1)
在从M-N个人中取出N个人来放入N个区间,按尽可能的安排喜好度最大的进去,形成安排第一批人的 喜好度最大解 f(2)
当(M<N或者已经有区间放不下人了)
M<N时 有些区间满了,去除掉满的区间 继续 上面的过程来求解最优解
           
但是这里面有个安排次序问题
比如从 1到N的次序来安排人的话,那么先安排的区间,对比其他区间是有优先权的,不同的优先权有不同的最优先解(因为取法不是取的所有情况,取的只是部分),要对不同的优先解比较来得出进一步修正的最优解
对这种优先权的排列来讲的话就有 (N*(N-1)........1)*N种选择 N小的情况下 还能容忍  如果N很大的话就很慢了,再考虑竞争的话 情况更加糟糕,解出来的也只是可能解
不是唯一解 这个才是硬伤
所以我放弃了这个解体思路
最优子结构摆脱不了优先权的困扰,所以不能够用上面最优子结构的方法来进行规划


自己觉得还算可以的解体思路:
1.先不管人对区间的排他性,即一个人可以占据多个区间
  
所做的工作很简单
对每个区间进行喜好度排序 ,就得到了 喜好度从大到小的一个二维数组表
设排序矩阵为Q  Q(i,j)表示j区间 喜好度排序为i位置的人的编号
对区间喜好度进行一个总和得到 f(max)
这个二维数组也可以这么组织,省去查表,提高效率
Q(i,j) (j为偶数,0=<j<2(N-1)) 表示j/2区间,喜好排序为i位置的人的编号
Q(i,j) (j为奇数1=<j<=2N-1)表示 j/2区间,喜好排序为i位置的人的喜好值
简单的说就是偶数放编号 紧接着放喜好值

根据 一个萝卜一个坑的原理 可能有倒霉蛋没有坑,那这些倒霉蛋只能寄托希望给占了多个空的人挪身子让坑了
怎么个挪法呢  是下面要解决的问题

2。找出占多个区间和没有区间的人 (因为它们矛盾了,要干仗)
 按照区间的大小  遍历矩阵Q  来制造一个M个人占用区间情况的二维矩阵O  
O是M*(N+1)的矩阵 ,0(i,j)表示的是 第i个人是否占用第j个区间(O(i,j)的值为 0或者1 ), O(i,N+1)表示的是第i个人占有几个区间的计数,计数大于1的 和 计数为0的分别表示:占用多坑和没有区间的人
占用唯一坑的人都是标注的1

3。对占多坑的人和没坑的人进行最优解的构造,也就是找出 让出的坑的喜好和 与填进去的喜好和 之差最小
   让坑的人 产生填坑的二维矩阵
   这个二维矩阵用C来表示 M1表示没人人数,N1表示区间数
   
    用数组b[i] (0=<i<M1)来表示没坑的人编号
    用数组a[j][2] (0=<j<N1)  a[j][0]表示让坑区间编号  a[j][1]表示容纳数   
    要计算C[i][j]的值 就得去到b[i]里面查编号,去数组a[j][0]去查找区间号,让后去到最初的喜好表去查找对应的值就是C[i][j]的值了
    用这个方法将矩阵C构造出来

    用这个新矩阵重复上面的 1 2 3步 直到所有的人都安排了,且占用区间数都是1
4。由于竞争存在的关系
   也就是 一个区间满其后的喜好和区间最后的喜好相同时 ,这个其后的喜好的人 可能已经占了一个坑或者他没有坑  两种情况
   极有可能产生多坑的不同组合?还没抽象出来。。。。。。。。构思中
   不过存在多坑的不同组合,也不过是将上面的 1 2 3 4重复一遍的过程

这样的求解过程是能得到唯一解的,而且可以在占用区间表中能反映出区间分配的情况

先上思路

[ 本帖最后由 zhu224039 于 2014-6-30 06:16 编辑 ]

我要成为嘿嘿的黑客,替天行道
2014-06-30 04:25
zhu224039
Rank: 8Rank: 8
等 级:贵宾
威 望:17
帖 子:862
专家分:792
注 册:2012-7-29
  得分:0 
M的个B 不说代码,想个思路都要一天而且还没想好  这个还只是初赛的题目,怎么去参加ACM比赛
fuck  天分太差了

我要成为嘿嘿的黑客,替天行道
2014-06-30 05:03
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
  得分:5 
没想好可以慢慢想,嘴上老挂着脏字会降低思考的能力。

重剑无锋,大巧不工
2014-06-30 10:18
azzbcc
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:江西财经大学
等 级:贵宾
威 望:81
帖 子:3293
专家分:12919
注 册:2012-11-4
  得分:5 
首先,这是一个二分图

再将 a[i] 分解为多个 1 ,得到 M 个区域,去匹配 M 个员工

然后可以用 KM 算法求最大权匹配


[fly]存在即是合理[/fly]
2014-06-30 15:07
ditg
Rank: 10Rank: 10Rank: 10
等 级:贵宾
威 望:13
帖 子:659
专家分:1520
注 册:2014-4-10
  得分:5 
可能跟楼主对题目的理解有偏差,题目只说是最优解,好像没说唯一解吧,证明如下:当M = N = 300时,全域解空间规模是300!,目前core2的运算速度就算简单加减法也就每秒百亿次级别,数量级差别太大,换句话说,对唯一解若采用遍历或类遍历算法估计很难满足要求,所以题目应该是求在自设算法下的最优解。

有两种思路可供参考:
1. 考虑到底层建模和多层神经网络相似,所以可采用神经网络求极值的方法;
2. 进化类算法,基础编码采用整数编码(matlab里randperm的实现方法)。
2014-06-30 18:42
快速回复:第二个用数学思想来写程序的小探索过程记录
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.066095 second(s), 8 queries.
Copyright©2004-2019, BCCN.NET, All Rights Reserved