これはまさにビンパッキング問題です。これもNP完全であるため、既知の多項式の解はありません(一般的な仮定は存在しませんが、まだ証明されていません)。
近似アルゴリズム、または比較的効率的な正確なアルゴリズムを探している場合、この問題は広く研究されています
PS-あなたが提案するランダムなアプローチはあなたに解決策を与えるでしょう、しかしそれは最適ではありません。
反例:
arr = [2,3,4,1] , size=5
アルゴリズムの可能な解決策は次のselect 3, select 1, select 4, select 2
とおりです。
[3,1],[4],[2]
最適なソリューションは[3,2],[4,1]
(-)貪欲なアプローチ(最も高いものを選択し、利用可能なビンに入れます-収まる場合は、新しいビンを「開く」)は、ランダム化されたソリューションよりもうまくいくと思いますが、それでもそうではありません反例で最適:
arr = [5,4,4,3,2,2] size = 10
貪欲は[5,4],[4,3,2],[2]
最適ですが[5,3,2],[4,4,2]
精度の損失に関して-これは、をMath.floor(double)
生成するために発生long
しますが、それをとして使用するとint
(理論的には、そうするとデータが失われる可能性があります)。ただし、intと。であるため、aMath.floor(Math.random() * input.length
の範囲内にあることが保証されているため、この場合は問題になりません。int
input.length
Math.random() < 1