山东大学:孙凯、姚相振、王棹,指导教师:黄淑祥 现的,所以我们考虑用算法实现 根据我们对满意度的理解及该模式下的网站的经营方案,如果要使得会员的满意度 达到最大,应该尽量满足会员订单之中偏爱度较小的碟片请求.根据我们的假设,会员提 交订单的时间是随机的,当网站在处理会员的订单请求时,必然存在一个处理次序问题, 我们假设处理次序仅与用户发出订单的次序有关 假设当前的订单已经按会员的请求顺序排列出来,会员被编号为1-1000,为了使得 总体的满意度最大,我们所要做的是尽量满足会员订单中偏爱度较小的请求,同时尽量 满足编号靠前的会员的请求.根据以上分析我们引入下面的算法解决分配方案 1),提取表2中的数据,经过一定的加工处理生成需求矩阵Met;,偏爱矩阵 Usermetr.矩阵Metr;反映了会员i对DVDj的偏爱程度,0表示会员对该DVD无需 求,1,2…n分别表示会员对DⅦ的偏爱程度,数值越小偏爱程度越高矩阵 Usermetr反 映了会员m偏爱度为n的对应的DVD编号 2),根据用户的偏爱度从低到高进行排序,偏爱度相同的按照会员编号进行排序, 构成序列A,B,其中A记录了序列第i项对应的会员编号,B记录了序列第i项对应 会员满足一定偏爱的DⅦD编号. 3),构建DD库存序列Sore,(i=1,2100,表示DVD当前的库存数构建会员定购 盘数序列 Check,表示会员j当前还需满足的DV盘数,显然分配前有 Cont1=3,(j=1,2…1000 4),构建与A序列等长的序列 Check,然后对A,B中的数据逐个检索,假设A中第 i项中会员的编号为k,B中第i项中DVD编号为l.如果Coun(k)>0并且Sore(l)>0,则 说明会员k希望得到l号DⅦD,已分配给会员k的光碟数不足三张,而l号DVD有库存,所以 可以把l号DVD分配给会员k, 7 Check(i=l, Count(k)=Count(k)-1, Store(0)=Store(0)-1 否则,如果Coun(k)=0,说明当前的会员k已经分配的三张光碟,如果Sore()=0, 说明会员k希望分配的l号DⅦD已经分完,显然这两种情况都不满足分配条件,故令 Check(i)=0.显然 Check中0,1分布反映了DVD的分配情况 5),统计 Check中的所有的1对应的会员编号及对应的DD编号,由于分配时仅考虑 的时会员对某一张DVD的定购请求是否满足而没有考虑用户请求盘数为三的要求,故上 述分配方案可能导致某些用户请求订单上的一张,或两张盘得到满足,显然对于这些用 户来说分配并未完成,故统计过程中仅可以记录已经分配三张碟片的会员编号,及其对 应的DⅦD编号 2005年全国大学生数学建模竞赛全国一等奖山东大学：孙凯、姚相振、王棹，指导教师：黄淑祥 2005 年全国大学生数学建模竞赛全国一等奖 7 现的,所以我们考虑用算法实现. 根据我们对满意度的理解及该模式下的网站的经营方案,如果要使得会员的满意度 达到最大,应该尽量满足会员订单之中偏爱度较小的碟片请求.根据我们的假设,会员提 交订单的时间是随机的,当网站在处理会员的订单请求时,必然存在一个处理次序问题, 我们假设处理次序仅与用户发出订单的次序有关. 假设当前的订单已经按会员的请求顺序排列出来,会员被编号为 1-1000,为了使得 总体的满意度最大,我们所要做的是尽量满足会员订单中偏爱度较小的请求,同时尽量 满足编号靠前的会员的请求.根据以上分析我们引入下面的算法解决分配方案: 1),提取表 2 中的数据,经过一定的加工处理生成需求矩阵 Metrij ,偏爱矩阵 UserMetrmn .矩阵 Metrij 反映了会员 i 对 DVDj 的偏爱程度,0 表示会员对该 DVD 无需 求,1,2….n 分别表示会员对 DVD 的偏爱程度,数值越小偏爱程度越高。矩阵UserMetrmn 反 映了会员 m 偏爱度为 n 的对应的 DVD 编号. 2),根据用户的偏爱度从低到高进行排序,偏爱度相同的按照会员编号进行排序, 构成序列 Ai , Bi .其中 Ai 记录了序列第 i 项对应的会员编号, Bi 记录了序列第 i 项对应 会员满足一定偏爱的 DVD 编号. 3),构建 DVD 库存序列 ,( 1, 2.....100) i Store i = ,表示 DVDi当前的库存数.构建会员定购 盘 数 序 列 Checki , 表 示 会 员 j 当 前 还 需 满 足 的 DVD 盘 数 , 显 然 分 配 前 有 3,( 1,2......1000) Count j j = = . 4),构建与 Ai 序列等长的序列Checki ,然后对 Ai , Bi 中的数据逐个检索,假设 Ai 中第 i 项中会员的编号为k , Bi 中第i 项中 DVD 编号为l .如果Count k( ) 0 > 并且 Store l( ) 0 > ,则 说明会员k 希望得到l 号DVD,已分配给会员k 的光碟数不足三张,而l 号DVD有库存,所以 可以把l 号 DVD 分配给会员k , 令 Check i( ) 1 = ,Count k Count k ( ) ( ) 1 = − , Store l Store l ( ) ( ) 1 = − . 否则,如果Count k( ) 0 = ,说明当前的会员 k 已经分配的三张光碟,如果 Store l( ) 0 = , 说明会员 k 希望分配的 l 号 DVD 已经分完,显然这两种情况都不满足分配条件,故令 Check i( ) 0 = .显然Checki 中 0,1 分布反映了 DVD 的分配情况. 5),统计Checki 中的所有的 1 对应的会员编号及对应的 DVD 编号,由于分配时仅考虑 的时会员对某一张 DVD 的定购请求是否满足而没有考虑用户请求盘数为三的要求,故上 述分配方案可能导致某些用户请求订单上的一张,或两张盘得到满足,显然对于这些用 户来说分配并未完成,故统计过程中仅可以记录已经分配三张碟片的会员编号,及其对 应的 DVD 编号