由题目: 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 编辑 ]
