0

わかりました、例は重要ではありません。私はそれをコンテキストに置くために使用していました。しかし、基本的に私は配列/配列リストからランダムな値を取得する方法を疑問に思っていますか?

私はこれを使ってみました:int random = (int)input[Math.floor(Math.random() * input.length)]; しかし、それは私がすでにcastそれを使っていたとしても、潜在的な精度の低下を浮き彫りにします。私はそれを間違ってキャストしましたか?

この例は実際には無関係であり、私はすべての質問に対する回答を受け入れます。当初、私は自分が正しい方向に進んでいるかどうかを確認するために、自分の影響を受けずに正しい答えを見たかったのです。

4

1 に答える 1

1

これはまさにビンパッキング問題です。これも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の範囲内にあることが保証されているため、この場合は問題になりません。intinput.lengthMath.random() < 1

于 2012-11-29T11:44:22.103 に答える