i*********7
发帖数: 348 | 1 题目：在3台机器上处理request，求最优分配（让总权重值尽可能高）
每台机器有权重，每个request也有权重。比如，将权重3的request放在权重1的机器上
处理，和将权重1的request放在权重3的机器上处理，得到一样的总权重值。也就是某
个request的实际权重等于他本身的权重乘以机器的权重。
一个Request 由 “开始时间，结束时间，请求机器id，类型，权重” 组成
机器则有两个属性“自身权重，机器id”
同一时间每台机器只能处理三个request
并且同类型的request在同一时间不能被多台机器同时处理。 比如类型1的request在时
间2已经在某机器上运行了，其它类型1的request就不能再被其它机器运行，即使它们
空闲。
本来想用dp解，结果发现想爆了头都想不出来递归式。哎，自己还是弱爆了。。=。=求
大家解答一下。 |
f*****e
发帖数: 2992 | 2 minimum cost flow，权重为xi*yj，m台机器，n个request，就有m*n条边，每边权重就是
前面那个。每台机器对应一个汇ti，所有类型j的request对应一个源sj，然后每台机器
ti到总汇t的capacity=3,同类型request sj到每个machine ti的capacity为1。总源s到
sj的capacity为类型j的request数目。
你用LP做也可以。
【在 i*********7 的大作中提到】
: 题目：在3台机器上处理request，求最优分配（让总权重值尽可能高）
: 每台机器有权重，每个request也有权重。比如，将权重3的request放在权重1的机器上
: 处理，和将权重1的request放在权重3的机器上处理，得到一样的总权重值。也就是某
: 个request的实际权重等于他本身的权重乘以机器的权重。
: 一个Request 由 “开始时间，结束时间，请求机器id，类型，权重” 组成
: 机器则有两个属性“自身权重，机器id”
: 同一时间每台机器只能处理三个request
: 并且同类型的request在同一时间不能被多台机器同时处理。 比如类型1的request在时
: 间2已经在某机器上运行了，其它类型1的request就不能再被其它机器运行，即使它们
: 空闲。
|
i***h
发帖数: 12655 | 3 这是贪婪算法吧
每个类型按权重从高到低排序，三个一组
然后每次权重最高的组和最高的机器配对 |
i***h
发帖数: 12655 | 4 嗯，好像还要考虑每个请求的执行时间
【在 i***h 的大作中提到】
: 这是贪婪算法吧
: 每个类型按权重从高到低排序，三个一组
: 然后每次权重最高的组和最高的机器配对
|
w****x
发帖数: 2483 | 5 这题用greedy得了, 假设request是不断近来了, 一个request的value就是weight/time
, 作个最大堆, 堆顶为value最大的, 一个一个从堆中取, 如果当前不合适(相同type正
在处理)就过掉取下一个, 直到找到一个符合条件的发送到处理任务<3的weight最大的
机器上去 |
