關於使箱子的最大負荷最小化的算法

-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

關於使箱子的最大負荷最小化的算法

回答

相關問題