关于使箱子的最大负荷最小化的算法

-1

有n箱子和m球。球与不同重量，说球i有重量w_i。是否有一种算法将球分配到x<n分箱中，以使这些分箱的最大负载最小化。关于使箱子的最大负荷最小化的算法

2011-06-28 Richard

...这样的......？ –

这个问题属于http://cstheory.stackexchange.com，但那里已经有很多包装问题，所以我不会迁移它。相反，我会将其作为主题关闭，并请您回顾该网站上已有的问题，并查看是否有任何问题可以回答您的问题。这里有一个搜索链接：http：//cstheory.stackexchange.com/search？q =包装 –

这相当于multiprocessor scheduling problem，它是NP完全的。换句话说：算法存在，但它们非常缓慢。

来源

2011-06-28 14:42:09

Aasmund几乎得到这个。 – Colin

这是一个伪装的散列函数问题。即您正在寻找最佳的散列函数。看看这个页面 - http://en.wikipedia.org/wiki/Hash_function

一般你想要一个随机密钥，你可以用w_i进行异或运算，然后拿结果模n来获得bin数。

注意：我花了最大的负载来表示每个垃圾箱的球数。如果要将每个垃圾箱的重量降至最低，则散列当然不起作用。

来源

2011-06-28 14:42:24 Colin

他对球数量的均匀分布不感兴趣（这是最佳散列函数会给出的），但是_weight_的均匀分布。 –

我相信你错了，Aasmund有正确的答案。我没有看到这个问题与哈希有什么关系，除了当然结果映射可以表示为哈希函数（但这很平凡，而且不是很有趣）。 –

btw - 我们并没有真正解决这个问题，但是对于np-完整问题的最优解决方案很容易描述;通过球的每一个可能的组合，运行到垃圾箱，并看看哪个给出了最好的结果:-) – Colin

关于使箱子的最大负荷最小化的算法

回答

相关问题