10

わかりました、問題があります。私はさまざまなサイズのボトルのセット「A」を持っており、すべて水で満たされています。次に、さまざまなサイズのボトルの別のセット「B」があり、すべて空です。

各セットの合計容量が同じであることを知って、A から B に水を移動したいと考えています。(つまり、セット A にはセット B と同じ量の水が含まれています)。

もちろん、これ自体は些細なことで、最初のボトルを B に取り、最初のボトルを A に注ぎ、いっぱいになるまで注ぎます。次に、B のボトルにまだ水が入っている場合は、A の 2 番目のボトルに進みます。

ただし、注ぐ回数の合計を最小限に抑えたいです (ボトルから別のボトルに注ぐアクション。水の量に関係なく、各アクションは 1 としてカウントされます)。

これを行うための貪欲なアルゴリズムを見つけたいと思います。それが不可能な場合でも、少なくとも効率的なアルゴリズムを見つけてください。ただし、効率はアルゴリズムの正確さに次ぐものです (次善のソリューションは必要ありません)。

もちろん、この問題は、個人の支出を管理するためのコンピューター プログラムにおける実際の問題の比喩にすぎません。

4

3 に答える 3

8

悪いニュース：この問題は、サブセット和からの削減によってNP困難です。数x1 、…、x n 、Sが与えられた場合、サブセット和の目的は、x iの一部のサブセットがSに合計されるかどうかを決定することです。容量x1 、…、xnおよびBのAボトルを作成します。 -容量Sおよび（x1 + …+ xn --S）のボトルを使用し、n回の注入で十分かどうかを判断します。

良いニュース：貪欲な戦略（つまり、空でないAを選択し、満たされていないBを選択し、停止するまで注ぐ）は2近似です（つまり、最適な注ぐ量の最大2倍を使用します）。最適なソリューションでは、少なくともmax（| A |、| B |）の注入を使用し、貪欲な使用では最大で|A|を使用します。+ | B |、貪欲な人が注ぐたびに、Aが排出されるか、Bが満たされ、出入りする必要がないためです。

近似スキーム（a（1 +ε）-任意のε> 0の近似）が存在する可能性があります。今では、近似不可能な結果が生じる可能性が高いと思います。近似スキームを取得するための通常のトリックは、ここでは適用されないようです。

ここに、実用的な正確なアルゴリズムにつながる可能性のあるいくつかのアイデアがあります。

A解決策が与えられたら、左の頂点と右の頂点、およびに注がれた場合に限り、からへBの（無向の）エッジを持つ2部グラフを描画します。解決策が最適である場合、私はサイクルがないと主張します。そうでなければ、サイクル内の最小の注入を排除し、サイクルの周りで失われた量を置き換えることができます。たとえば、私が注ぐ場合abab

a1 -> b1: 1
a1 -> b2: 2
a2 -> b1: 3
a2 -> b3: 4
a3 -> b2: 5
a3 -> b3: 6

a1 -> b1それから私はそのように注ぐことによって排除することができます：

a2 -> b1: 4 (+1)
a2 -> b3: 3 (-1)
a3 -> b3: 7 (+1)
a3 -> b2: 4 (-1)
a1 -> b2: 3 (+1)

これで、グラフにサイクルがないため、エッジ（注入）の数をとしてカウントできます|A| + |B| - #(connected components)。ここでの唯一の変数は、最大化したい連結成分の数です。

欲張りアルゴリズムは、サイクルのないグラフを形成すると私は主張します。最適解の連結成分が何であるかを知っていれば、それぞれに欲張りアルゴリズムを使用して、最適解を得ることができます。

このサブ問題に取り組む1つの方法は、動的計画法を使用して、sum（X）== sum（Y）となるようにAのすべてのサブセットペアXとBのYを列挙し、これらを正確なカバーアルゴリズムにフィードすることです。もちろん、どちらの手順も指数関数的ですが、実際のデータではうまく機能する可能性があります。

于 2011-02-27T14:04:07.437 に答える
3

これが私の見解です：

  1. 両方のセットでまったく同じサイズのボトルを識別します。これは、これらの同じサイズのボトルに 1 対 1 で注ぐことを意味します。
  2. Aの残りのボトルを容量の降順に並べ替え、Bの残りのボトルを昇順に並べ替えます。A のソートされたリストを B に注ぐときに必要な注ぎの数を計算します。

更新:ステップ 2 を注ぐたびに、ステップ 1 を繰り返します ( Steve Jessopによって提案された最適化ステップ)。すべての水が移動するまですすぎ、繰り返します。

于 2011-02-27T13:45:19.053 に答える
0

私はこれが注ぎの最小数を与えると思います：

import bisect

def pours(A, B):
    assert sum(A) == sum(B)
    count = 0
    A.sort()
    B.sort()
    while A and B:
        i = A.pop()
        j = B.pop()
        if i == j:
            count += 1
        elif i > j:
            bisect.insort(A, i-j)
            count += 1
        elif i < j:
            bisect.insort(B, j-i)
            count += 1
    return count

A=[5,4]
B=[4,4,1]
print pours(A,B)
# gives 3

A=[5,3,2,1] 
B=[4,3,2,1,1]
print pours(A,B)
# gives 5

英語では次のように書かれています。

  • sum(A) > sum(B)両方のリストの合計が同じであることを主張します (またはsum(A) < sum(B)が true の場合、アルゴリズムは引き続き機能すると思います)
  • 2 つのリスト A と B を取得し、両方を並べ替えます

A は空ではなく、B は空ではありません。

  • A から i (最大) を取得し、B から j (最大) を取得します。
  • i が j に等しい場合、i を j に注ぎ、1 を数える
  • i が j より大きい場合、i を j に注ぎ、残りの ij を A に戻し (挿入ソートを使用)、1 を数える
  • i が j より小さい場合、i を j に注ぎ、残りの ji を B に戻し (挿入ソートを使用)、1 を数える
于 2011-02-27T13:45:33.933 に答える