複雜倉與倉重

Question

的定義的功能，我有以下問題所困擾包裝：

鑑於n整數，將它們放入m箱，使各倉的總和最小化。訣竅是，一旦數字被放置在箱中，總重量/成本/倉的總和在非標準的方式計算：

weight_of_bin = Sigma - k * X哪裏Sigma是整數在bin k總和是多少的整數 X是位於箱中的整數具有相同的主要除數的數量。換句話說，通過將具有許多主要因數的數字組合在一起，並通過將不同數量的數字放在不同的分箱中，我們可以在總數中實現一些「節省」。

我使用垃圾包裝配方，因爲我懷疑問題是NPhard，但我無法找到證明。我不是一個數理論的人，並且對倉的重量取決於倉內物品的事實感到困惑。

這種類型的問題有硬度結果嗎？

P.S.我只知道這些數字是整數。對於問題中涉及的最大整數沒有明確的限制。

謝謝你可以給的任何指針。

Answer 1

這不是一個完整的答案，但希望它給你一些事情要考慮。

首先，通過澄清：你知道整數的主要因子是什麼？在問題的輸入中查找整數的所有主要因子是很困難的。因式分解不是已知的NP完全的，但也不知道是否在P中。如果您還不知道投入的因式分解，那麼這可能足以使這個問題變得「困難」。

一般情況下，我預計這個問題至少和垃圾箱一樣困難。一個簡單的參數來表明這是可能的，沒有一個整數給出有任何共同的素因子（例如，如果你有一組不同的素數）。在這種情況下，由於垃圾箱的重量僅僅是標準重量，因此問題減少到標準垃圾箱包裝。如果你對可能有多少個常見因數有保證，那麼你可能會做得更好，但可能並不普遍。

存在bin打包的變體，稱爲VM packing（基於打包基於內存要求的虛擬機的想法）允許對象共享空間（如共享虛擬內存頁面）。你的目標函數，如果你根據「共享」素數因子減去一個術語，這讓我想起了這一點。即使在虛擬機打包的情況下，這個問題也是NP難題。如果共享具有良好的層次結構，則存在良好的近似算法，但它們仍然只是近似值。