最初の試行では、単純な動的計画法の問題として扱ってください。
したがって、封筒のリストの各位置について、左から右に作業し、残せる可能性のある文字の各セットについて、そのポイントに到達する方法の数を計算します. 先に進むのは簡単です。セットを取得するだけで、そこに到達する方法がいくつあるかがわかります。次に、次の封筒に入れることができる文字ごとに、結果のセットの合計を方法の数だけ増やしますその点に到達するために。封筒のリストの最後に到達すると、残りの文字を 0 にする方法がいくつあるかがわかります。これが答えです。
2 番目の例では、次のように進行する可能性があります。
Step 0: next envelope 1
{1: 2, 2: 2, 3: 1}: 1
-> {1: 2, 2: 1, 3: 1}
-> {1: 2, 2: 2}
Step 1: next envelope 1
{1: 2, 2: 1, 3: 1}: 1
-> {1: 2, 2: 1}
-> {1: 2, 3: 1}
{1: 2, 2: 2}: 1
-> {1: 2, 2: 1}
Step 2: next envelope 2
{1: 2, 2: 1}: 2
-> {1: 1, 2: 1}
{1: 2, 3: 1}: 1
-> {1: 1, 3: 1}
-> {1: 2}
Step 3: next envelope 2
{1: 1, 2: 1}: 2
-> {2: 1}
{1: 1, 3: 1}: 1
-> {1: 1}
-> {3: 1}
{1: 2}: 1
-> {1: 1}
Step 4: next envelope 3
{2: 1}: 2
-> {}
{1: 1}: 2
-> {}
{3: 1}: 1
// Dead end.
Step 5:
{}: 4
これは機能し、要求した計算範囲に到達します。15 の場合、2^15 = 32768 の可能なサブセットを追跡することができ、これは非常に実行可能です。ただし、20 前後でメモリが不足し始めます。
これを改善できますか？答えは、できるということです。私たちのエネルギーの大部分は、たとえば、これまでに 8 とラベル付けされた封筒と 9 とラベル付けされた封筒を使用したかどうかを思い出すことに費やされます。しかし、私たちはそれを気にしません。終了する方法がいくつあるかを決定するのは、封筒 8 を使用したか 9 を使用したかではなく、パターンです。x 封筒と y 通の手紙が残っているラベルはいくつありますか。どのラベルがどれであるかではなく、いくつあるかだけです。
したがって、その情報だけを追跡すると、各ステップで、封筒の残りが最も多いラベルの付いた封筒を取得できます。同点の場合は、残りの文字数が最も少ない封筒を選択しますネクタイ、どちらを取得するかは本当に気にしません）。前と同じように計算を行いますが、中間状態ははるかに少なくなります。(あなたが持っている封筒をそのまま並べて巻き上げるわけではありません。しかし、封筒を使って最終的な手紙を安定してソートすると、上記のリストが返されます。)
封筒や手紙が残っているラベル[x y]: zがあるという意味で表記してみましょう。そして、そのようなラベルのリストがあります。次に、の例は次のように表すことができます。トランジションでは、ラベルの 1 つを取得して、もう一方のラベルの文字を使用するか ( への遷移を与える)、ラベルの 1 つを取得し、ラベルの文字を使用します(への移行)。zxy1 1 2 2 3{[2 2]: 2, [1 1]: 1}[2 2]{[2 1]: 1, [1 2]: 1, [1 1]: 1}[2 2][1 1]{[2 2]: 1, [1 2]: 1, [1 0]: 1}
計算を実行しましょう。状態、そこに到達する方法の数、およびあなたが行う遷移をリストします。
Step 1:
{[2 2]: 2, [1 1]: 1}: 1
-> 1 * {[2 1]: 1, [1 2]: 1, [1 1]: 1}
-> 1 * {[2 2]: 1, [1 2]: 1, [1 0]: 1}
Step 2:
{[2 1]: 1, [1 2]: 1, [1 1]: 1}: 1
-> 1 * {[1 1]: 3}
-> 1 * {[1 1]: 1, [1 2]: 1, [1 0]: 1}
{[2 2]: 1, [1 2]: 1, [1 0]: 1}: 1
-> 1 * {[1 2]: 1, [1 1]: 1, [1 0]: 1}
Step 3:
{[1 1]: 3}: 1
// This is 2x because once the label is chosen, there are 2 letters to use.
-> 2 * {[0 1]: 1, [1 0]: 1, [1 1]: 1}
{[1 1]: 1, [1 2]: 1, [1 0]: 1}: 2
-> 1 * {[1 0]: 1, [1 2]: 1, [0 0]: 1}
-> 1 * {[1 1]: 2, [0 0]: 1}
{[1 2]: 1, [1 1]: 1, [1 0]: 1}: 1
-> 1 * {[1 1]: 2, [0 0]: 1}
-> 1 * {[1 2]: 1, [1 0]: 1, [0 0]: 1}
Step 4:
{[0 1]: 1, [1 0]: 1, [1 1]: 1}: 2
-> 1 * {[1 1]: 1, [0 0]: 2}
-> 1 * {[1 0]: 1, [0 1]: 1, [0 0]: 1}
{[1 0]: 1, [1 2]: 1, [0 0]: 1}: 2
-> 1 * {[1 1]: 1, [0 0]: 2}
{[1 1]: 2, [0 0]: 1}: 2
-> 1 * {[1 0]: 1, [0 1]: 1, [0 0]: 1}
Step 5:
{[1 1]: 1, [0 0]: 2}: 4
// dead end
{[1 0]: 1, [0 1]: 1, [0 0]: 1}: 4
-> 1 * {[0 0]: 3}
なので答えは4です。
これは途方もない量の作業のように思えるかもしれません - 列挙するよりもはるかに多くの作業です。そしてそうだった！
ただし、スケーリングします。100 通の手紙と封筒で試してみると、すぐに実行されるはずです。