2

問題定義

n同じ容量のバケットがm隣り合っています。1 つのバケツから右のバケツに水を注ぐことができます。目標は、すべてのバケツを別の容器に空にすることですが、空にできるのは右端のバケツだけです。それらはそれぞれ、特定の初期量の水を持っています。wここで0 <= w <= m、 とwは整数です。6 6 -> 3 9 で 3 だけを注ぐ場合、それは許可されません。注ぐ場合は、できるだけ注ぐ必要があるため、合法的な動きは 6 6 -> 2 10 になります。

すべてのバケツを空にするために必要な移動の最小数は? バケットの最大数は 1000 で、最大容量は 100 です。

例

例 1

4 つのバケツ容量 10 以下の量の水: 4 0 6

答えは 4 0 6 -> 0 4 6 -> 0 0 10 -> 0 0 0 で、3 手です。

例 2

3 バケット容量 10、8 9 3

8 9 3 -> 8 2 10 -> 0 10 10 -> 0 10 0 -> 0 0 10 -> 0 0 0 = 合計 5 回の移動

最初にさまざまな種類のアルゴリズム (貪欲、動的、バックトラッキングなど) で試してみましたが、どれもうまくいかないようでした。私はかなり直感的な解決策を見つけたと思っていましたが、これらの答えをチェックするプログラムはそれが間違っていると私に言ったので、間違っているかもしれません. もう1つのことは、このプログラムは以前に正解を拒否したため、よくわかりません.

これが私の解決策です：

各バケットの前にあるすべてのバケットの合計を計算し、その数の上限をバケットの容量で割って、それらの数をすべて加算します。

例: 6 6 6 6 6 -> 6 12 18 24 30

ceil(6/10) ceil(12/10) ceil(18/10) ceil(24/10) ceil(30/10) = 1 + 2 + 2 + 3 + 3 = 11

それが正しい答えです: 6 6 6 6 6 -> 6 2 10 6 6 -> 0 8 10 6 6 -> 0 8 10 2 10 -> 0 8 2 10 10 -> 0 0 10 10 10 -> 0 0 10 10 0 -> 0 0 10 0 10 -> 0 0 10 0 0 -> 0 0 0 10 0 -> 0 0 0 0 10 -> 0 0 0 0 0 = 11 ステップ

ロジックはL、特定のバケツの前に 1 リットルの水がある場合、少なくともceil(L/Capacity)その位置を通過する動きがなければならないということです。これまでに約 30 のテスト ケースを試しましたが、すべてうまくいきました。反例を見つけたと思うたびに、手で何度か試してみると、自分が間違っていることに気づきました。問題は、これが正しい答えだと確信していますが、このようなことを証明する方法がわからないか、単に間違っている可能性があることです。

この答えが正しいかどうか誰か教えてもらえますか?

4

4 に答える 4

-1

驚くほど簡単な解決策があります。

移動の最適な数は であることが知られていますSum(0<=i<N: Pi\C)。ここで\、超過分による整数の除算を表しPi、接頭辞の合計を の形式で表しBます。

例：

 6  6  6  6  6
 6 12 18 24 30
 1  2  2  3  3 => 11

常に最適数を 1 単位減らす動きを選択すれば十分です。この移動は、 に関する線形時間で見つけることができますN。(ヒント:Pi\C移動が減少するものを見つけてください。)

 2>10  6  6  6
 2 12 18 24 30
 1  2  2  3  3 => 11

 6  2>10  6  6
 6  8 18 24 30
 1  1* 2  3  3 => 10

 6  6  2>10  6
 6 12 14 24 30
 1  2  2  3  3 => 11

 6  6  6  2>10
 6 12 18 20 30
 1  2  2  2* 3 => 10

 6  6  6  6  0>
 6 12 18 24 24
 1  2  2  3  3 => 11

全体の複雑さはO(N.M)で、Mは最適な移動数です。

B= [6, 6, 6, 6, 6]
C= 10

# Show the current state
print B

 # Append the container
B.append(- sum(B))

# Loop until all buckets are empty
while B[-1] != 0:
    # Emulate the quotient by excess
    Prefix= C - 1

    # Try all buckets
    for i in range(len(B) - 1):        
        # Amount transferable
        A= min(B[i], C - B[i + 1])

        # Evaluate the move from i to i+1
        Prefix+= B[i]
        if (Prefix - A) / C < Prefix / C:
            # The total count will decrease, accept this move
            B[i]-= A
            B[i + 1]+= A
            break

    # Show the current state
    print B[:-1]

>>> 
[6, 6, 6, 6, 6]
[6, 2, 10, 6, 6]
[0, 8, 10, 6, 6]
[0, 8, 10, 2, 10]
[0, 8, 2, 10, 10]
[0, 0, 10, 10, 10]
[0, 0, 10, 10, 0]
[0, 0, 10, 0, 10]
[0, 0, 0, 10, 10]
[0, 0, 0, 10, 0]
[0, 0, 0, 0, 10]
[0, 0, 0, 0, 0]

アルゴリズムの終了の証明は、最適数の公式の有効性にかかっています。

于 2014-04-16T15:13:20.600 に答える
-1

これは解決策ではありませんが、ブルート フォースによって、特定の構成から移動の最小数を見つける Python コードです。正当な動きのすべてのシーケンスが試行され、最短の長さが報告されます。

B= [6, 6, 6, 6, 6] # Buckets state

M= sum(B) * len(B) # Gross upper bound
B.append(- sum(B)) # Append the container

def Try(N):
    global M

    # Check if we have found a better solution
    if B[-1] == 0 and N < M:
        M= N

    # Try every possible move from i to i+1
    for i in range(len(B) - 1):
        # Amount transferable
        D= min(B[i], 10 - B[i + 1])

        if D > 0:
            # Transfer
            B[i]-= D
            B[i + 1]+= D

            # Recurse
            Try(N+1)

            # Restore
            B[i]+= D
            B[i + 1]-= D

Try(0)
print M, "moves"

>>>
11 moves
于 2014-04-16T09:34:20.967 に答える
-1

正しいアルゴリズムの設計に影響を与える可能性のあるいくつかのポイント:-

  1. 右端のフル バケットは直接廃棄できます。合計ステップの右端の n 個のバケットに n*(n+1)/2 を追加するだけです。
  2. 右端のバケットが満杯でない場合は、前のバケットが満杯であるか、右端を満杯にすることができるかどうかを確認してから、条件が満たされるか最初のバケットに到達するまで、そのバケットを再帰的に満杯にすることを試みます。次に、バケツがいっぱいになるまで、または他が空になるまでバケツを注ぎ、ステップを数えます。
  3. バケツが 1 つだけになるかなくなるまで、1 から 2 を繰り返します。
  4. バケツが 1 つ残っている場合は空にします。

例:-

given 4 0 6 

1. fails 
2. last bucket is not empty hence try to pour second last but it is also empty 
   pour 4 into bucket 1 and then bucket 1 into bucket 2 . Hence after this step  
   4 0 6 => 0 4 6  => 0 0 10
3. 1 bucket left so 4
4. empty bucket 0 0 10 => 0 0 0




 given 8 9 3

   iteration 1 : 8 9 3 => 8 2 10 
   iteration 2 : 8 2 10 => 8 2 0  and  8 2 0 => 0 10 0
   iteration 3 : 0 10 0 => 0 0 10 => 0 0 0


 given 6 6 6 6 6

   iteration 1 : 6 6 6 6 6 => 6 6 6 2 10 
   iteration 2 : 6 6 6 2 10 => 6 6 6 2 0 && 6 6 6 2 0 => 6 2 10 2 0 => 6 2 2 10 0
   iteration 3 : 6 2 2 10 0 => 6 2 2 0 10 => 6 2 2 0 0 && 
                 6 2 2 0 0 => 0 8 2 0 0 => 0 0 10 0 0  
   iteration 4 : 0 0 10 0 0 => 0 0 0 10 0 => 0 0 0 0 10 => 0 0 0 0 0

時間の複雑さ :-単純な実装はO(n^2)、1 回の反復で少なくとも 1 つの右端のバケットがO(n)計算で空になるためです。

于 2014-04-16T11:17:40.763 に答える
-1

ここに問題に関する私の発見があります

まず、ゲームのルールを確認しましょう。

  • ルール 1:一番右のバケツがいっぱいになった場合にのみ、すべてを破棄できます

  • ルール 2:10-bucket[i+1]任意の場所から 1bucket[i]リットルまで、何リットルでも廃棄できます。bucket[i+1]

次の特殊なケースを考えてみましょう。

  1. シフト:第 2 バケットを 3 回シフトしてから廃棄0, 10, 0, 0, 0する場合

  2. Merge : 2 41 番目のバケットを 2 番目のバケットにマージして取得できる場合0 6

  3. 完全マージ:マージ6 4し0 10て 2 番目のバケットがいっぱいになる場合、最適な完全マージでは現在のバケットに 0 が残ります

結論:次の戦略をお勧めします。左から右への右から左への順次破棄、完全マージを行い、それを破棄にシフトします。

注: これは、この問題に最適なアルゴリズムではありません

void solution (int bucket [], const int size)
{
    for (int i=size-1; i>=0; i--)
    {
        // find a non-empty bucket
        if (bucket[i] > 0)
        {
            // bucket need to be filled
            if (bucket[i] < 10)
                for (int j=i-1; j>=0; j--)
                {
                    // -------------------
                    // fill bucket[i] from previous
                    //        buckets and count moves
                    // -------------------

                    if (bucket[i] == 10)
                        break;
                }

            bucket[i]=0; // (size-i) shift + 1 dispose
            moves = moves + (size-i) + 1;
        }
    }
}
于 2014-04-16T08:39:02.703 に答える