【急问】为什么这个夏天院里草变黄得厉害？ - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>gardening - 拈花惹草

【急问】为什么这个夏天院里草变黄得厉害？

【急问】为什么这个夏天院里草变黄得厉害？# gardening - 拈花惹草

i*72016-09-12 07:09

1 楼

题目：在3台机器上处理request，求最优分配（让总权重值尽可能高）
每台机器有权重，每个request也有权重。比如，将权重3的request放在权重1的机器上
处理，和将权重1的request放在权重3的机器上处理，得到一样的总权重值。也就是某
个request的实际权重等于他本身的权重乘以机器的权重。
一个Request 由 “开始时间，结束时间，请求机器id，类型，权重” 组成
机器则有两个属性“自身权重，机器id”
同一时间每台机器只能处理三个request
并且同类型的request在同一时间不能被多台机器同时处理。比如类型1的request在时
间2已经在某机器上运行了，其它类型1的request就不能再被其它机器运行，即使它们
空闲。
本来想用dp解，结果发现想爆了头都想不出来递归式。哎，自己还是弱爆了。。=。=求
大家解答一下。

m*l2016-09-12 07:09

2 楼

去店里买的话需要打印email，有mm收到的话能转发我不？多谢啦
x********[email protected]

D*62016-09-12 07:09

3 楼

德州的暴热天气，前几年都没事，只有今年，house前后院的草如日俱黄，而且越来越
稀，急死了。。。请教版上高手，原因是下面哪个，该怎么办？
A. 天气太热太晒了，热/干死了。
B. 今年春天我把家前后院的浇水喷头设置成自动隔一天的早上六点喷一次水浇草，每
次13分钟。以前都没有，今年才这样，难道这是主因？是浇水过于频繁而致黄？
C. 好几年没有施肥（fertilization）了。
D. 其它。
谢谢指点！

f*e2016-09-12 07:09

4 楼

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就不能再被其它机器运行，即使它们
: 空闲。

d*c2016-09-12 07:09

5 楼

同求，d****[email protected]

【在 m******l 的大作中提到】

: 去店里买的话需要打印email，有mm收到的话能转发我不？多谢啦
: x********[email protected]

w*e2016-09-12 07:09

6 楼

感觉是A+C，我家有段时间不下雨的时候，被晒的多的那块草地明显发黄，自己怎么浇
水也没用。下了几场暴雨就绿回来了

【在 D******6 的大作中提到】

: 德州的暴热天气，前几年都没事，只有今年，house前后院的草如日俱黄，而且越来越
: 稀，急死了。。。请教版上高手，原因是下面哪个，该怎么办？
: A. 天气太热太晒了，热/干死了。
: B. 今年春天我把家前后院的浇水喷头设置成自动隔一天的早上六点喷一次水浇草，每
: 次13分钟。以前都没有，今年才这样，难道这是主因？是浇水过于频繁而致黄？
: C. 好几年没有施肥（fertilization）了。
: D. 其它。
: 谢谢指点！

i*h2016-09-12 07:09

7 楼

这是贪婪算法吧
每个类型按权重从高到低排序，三个一组
然后每次权重最高的组和最高的机器配对

c*a2016-09-12 07:09

8 楼

同求
c*******[email protected]

j*p2016-09-12 07:09

9 楼

草发黄是因为浇水少。
蔬菜叶子发黄是因为水大了。

i*h2016-09-12 07:09

10 楼

嗯，好像还要考虑每个请求的执行时间

【在 i***h 的大作中提到】

: 这是贪婪算法吧
: 每个类型按权重从高到低排序，三个一组
: 然后每次权重最高的组和最高的机器配对

c*a2016-09-12 07:09

11 楼

同求
c*******[email protected]

f*c2016-09-12 07:09

12 楼

我觉得也是水少了

w*x2016-09-12 07:09

13 楼

这题用greedy得了, 假设request是不断近来了, 一个request的value就是weight/time
, 作个最大堆, 堆顶为value最大的, 一个一个从堆中取, 如果当前不合适(相同type正
在处理)就过掉取下一个, 直到找到一个符合条件的发送到处理任务<3的weight最大的
机器上去