J*******i
发帖数: 2162 | 1 有N个整数，M个bucket，每个bucket都可以装至少N个整数
一个bucket的value等于放入它的所有整数的和
现求解一种分配方法，使之 minimize(the max value of all buckets)
看起来像bin packing问题，但好像又不是~ |
J*******i
发帖数: 2162 | 2 就是你往一个bucket可以装从0个到N个数，都可以 |
g*********s
发帖数: 1782 | 3 unsigned int or int?
【在 J*******i 的大作中提到】
: 有N个整数，M个bucket，每个bucket都可以装至少N个整数
: 一个bucket的value等于放入它的所有整数的和
: 现求解一种分配方法，使之 minimize(the max value of all buckets)
: 看起来像bin packing问题，但好像又不是~
|
J*******i
发帖数: 2162 | 4 unsigned int is fine
【在 g*********s 的大作中提到】
: unsigned int or int?
|
g*********s
发帖数: 1782 | 5 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********s
发帖数: 133 | 6 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*******i
发帖数: 2162 | 7 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******n
发帖数: 4965 | 8 就是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 的大作中提到】
: 有N个整数，M个bucket，每个bucket都可以装至少N个整数
: 一个bucket的value等于放入它的所有整数的和
: 现求解一种分配方法，使之 minimize(the max value of all buckets)
: 看起来像bin packing问题，但好像又不是~
|
