3

これは、ここに投稿された質問のサブセットです。

B={x1, x2, ..., xn}一定量のバケツのセットと一定量の液体が入ったバイアルの セットが与えられた場合、V={v1, v2, ..., vn }バイアルをすべて 1 つのバケツに注ぐ必要があると仮定して、バケツの数がバイアルの内容物で満たされることを証明する最良の方法は何ですか。オーバーフローは許可されます。

ここでのいくつかの明らかな不変条件は、バケット|B|のカーディナリティがバイアルのカーディナリティ以下でなければならず|V|、バケットの合計量Sum(B)がバイアルの合計量以下でなければならないということです。Sum(V)

これはよく知られた計算問題ですか？もしそうなら、これを C# で表現するための単純な LINQ ソリューションを作成できますか?

これは、Eric Lippert がブログに書いていたような気がします ;-)。

4

1 に答える 1

3

同じサイズの 2 つのバケットがあり、Sum(B) = Sum(V) であるこの問題のインスタンスを考えてみましょう。これは、バイアルを 2 つのバケツに均等に分配する必要があることを意味します。そうしないと、一方がオーバーフローし、もう一方に十分な量が残りません。これは分割問題と呼ばれ、 NP 完全であることが知られています。

編集： もちろん、NP完全性は問題が解決できないという意味ではなく、実行時間が入力のサイズ（この場合、最大のバケットサイズのlog2）で指数関数的になるというだけです。

バケツを満たすのに必要な液体の最小量 (こぼれを含む) を見つけることができれば、問題を解決するには、バケツごとにこれを行い、各バケツの後に使用可能なバイアルのセットから使用済みのバイアルを削除するだけです。

動的計画法を使用してこれを行うことができます。

  • 所定のバケット b について、サイズ 0 からボリューム (b) までのすべてのバケットを考慮します。
  • サイズ0のバケツは明らかに液体を必要としません
  • 各サイズ s について、次のようなバイアル v を見つけます。
    • s-volume(v) の解は v を使用しません
    • (s-volume(v) に使用される液体の量) + volume(v) が最小化されます
  • このすべてが終わると、バケツ b を満たすために使用されるバイアルが得られます。次に、使用可能なバイアルのセットからそれらを削除し、次のバケットに移動します.
于 2013-05-24T21:22:35.807 に答える