attic fan noise - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Living

attic fan noise

attic fan noise# Living

J*i2010-08-10 07:08

1 楼

有N个整数，M个bucket，每个bucket都可以装至少N个整数
一个bucket的value等于放入它的所有整数的和
现求解一种分配方法，使之 minimize(the max value of all buckets)
看起来像bin packing问题，但好像又不是~

n*e2010-08-10 07:08

2 楼

最近这个热啊。刚在屋顶（roof不是ceiling）装了一个roof top vent，蘑菇状带电扇
的那种。可
是在二楼卧室里和走道上能听见声音啊，正常吗？
这玩意儿到底有多大用处？跟锅盖似的，在屋顶挺不好看的。想多开几个口子，装几个
dormer
vents，不带电扇那种。不知道这决定是不是比较傻。房子在南加，夏天这叫一个热啊
。快热傻了。

J*i2010-08-10 07:08

3 楼

就是你往一个bucket可以装从0个到N个数，都可以

z*n2010-08-10 07:08

4 楼

LA今年奇了，每天半夜冷死，觉得快冻感冒了
每天都是五十多度到80多度，温差太大了

【在 n***e 的大作中提到】

: 最近这个热啊。刚在屋顶（roof不是ceiling）装了一个roof top vent，蘑菇状带电扇
: 的那种。可
: 是在二楼卧室里和走道上能听见声音啊，正常吗？
: 这玩意儿到底有多大用处？跟锅盖似的，在屋顶挺不好看的。想多开几个口子，装几个
: dormer
: vents，不带电扇那种。不知道这决定是不是比较傻。房子在南加，夏天这叫一个热啊
: 。快热傻了。

g*s2010-08-10 07:08

5 楼

unsigned int or int?

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

: 有N个整数，M个bucket，每个bucket都可以装至少N个整数
: 一个bucket的value等于放入它的所有整数的和
: 现求解一种分配方法，使之 minimize(the max value of all buckets)
: 看起来像bin packing问题，但好像又不是~

J*i2010-08-10 07:08

6 楼

unsigned int is fine

【在 g*********s 的大作中提到】

: unsigned int or int?

g*s2010-08-10 07:08

7 楼

then actually we can assume positive int, as zero doesn't matter.
sounds like a job assignment/scheduling problem:
given n task with different execution time and m workers, assign the task
to workers such that the task can be finished at the earliest time.
Job shop scheduling
http://en.wikipedia.org/wiki/Job_shop_scheduling

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

: unsigned int is fine

i*s2010-08-10 07:08

8 楼

This is NP complete. Suppose we have only 2 buckets, and a set of numbers.
Then the multiset partitioning problem (NPC) can be reduced to this problem.

J*i2010-08-10 07:08

9 楼

Thanks a lot for the reference!

task

【在 g*********s 的大作中提到】

: then actually we can assume positive int, as zero doesn't matter.
: sounds like a job assignment/scheduling problem:
: given n task with different execution time and m workers, assign the task
: to workers such that the task can be finished at the earliest time.
: Job shop scheduling
: http://en.wikipedia.org/wiki/Job_shop_scheduling

c*n2010-08-10 07:08

10 楼

就是binpacking 啊。
这题的decision 形式就是
given bins of bucket size X , N integers . X < sum(N)
and given bucket count M, is it possible to pack all N integers into
buckets?
decision---optimization 转换是search X,
original bin packing 的转换是search M

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