コンテンツにスキップ

14.8   演習

14.8.1   確認問題

1.   動的計画法が適している場面

ある生徒は、「漸化式を書けるなら、必ず動的計画法を使うべきです」と言いました。 次の 3 つの処理には、動的計画法、バックトラッキング、または dp テーブルを作らないループや数式のどれが適しているかを判断し、重要な理由を 1 つ書いてください。

  1. 額面 [1, 3, 4] の硬貨を使って金額 6 を作るときの最小硬貨枚数を求める。各硬貨は何度でも使える。
  2. [1, 2, 3] のすべての順列を出力する。

  3. \(1 + 2 + \dots + n\) を計算する。

    動的計画法が適していると判断した処理については、dp[i] が何を表すかも説明してください。

解答

  1. 動的計画法が適しています。dp[i] を、金額 i を作るのに必要な最小硬貨枚数とします。 i 以下の各硬貨 c について、dp[i-c] + 1 を答えの候補とし、 それらの候補の最小値を選べます。異なる選び方でも同じ金額を繰り返し扱い、より大きな金額の最適解をより小さな金額の最適解から作れるためです。 金額 6 の答えは 2 で、3 + 3 と選びます。

  2. バックトラッキングを使うべきです。すべての 6 通りの順列を 1 つずつ生成する問題なので、1 つの選択を試して探索を続け、 選択を取り消して別の分岐を試すバックトラッキングが使えます。どのような方法でも、これらの順列を実際に出力するには列挙を省けません。

  3. ループまたは等差数列の公式で十分です。S(i) = S(i-1) + i という漸化式は書けますが、S(i) の計算が依存するのは 1 つ前の S(i-1) だけで、 各部分和は 1 回だけ計算すればよく、重複部分問題がありません。そのため、dp テーブルは不要です。「漸化式を書ける」ことと「動的計画法が必要である」ことは同じではありません。

2.   ナップサック表の 1 つの値を求める

0-1 ナップサック問題を考えます。品物の重さは wgt = [1, 2, 3]、価値は val = [5, 11, 15]、ナップサックの容量は 4 です。 dp[i][c] は、先頭から \(i\) 個の品物だけを考え、ナップサックの容量上限が \(c\) のときに得られる最大価値を表します。 ナップサックをちょうど満たす必要はありません。

ここでは状態 dp[3][4] だけを計算します。dp[2][4] = 16、dp[2][1] = 5 であることが分かっています。

  1. 3 番目の品物を選ばない場合、候補となる価値はいくつですか？
  2. 3 番目の品物を選ぶ場合、容量はいくつ残り、候補となる価値はいくつですか？
  3. dp[3][4] はいくつにすべきですか？どの品物を選んだことに対応しますか？
解答

  1. 3 番目の品物を選ばない場合は、最初の 2 つの品物による結果をそのまま使うため、候補となる価値は dp[2][4] = 16 です。

  2. 3 番目の品物の重さは 3 なので、入れた後の残り容量は \(4-3=1\) です。候補となる価値は dp[2][1] + 15 = 5 + 15 = 20 です。

  3. 16 と 20 を比較して、dp[3][4] = 20 とします。これは 1 番目と 3 番目の品物を選ぶことに対応し、 総重量は \(1+3=4\)、総価値は \(5+15=20\) です。

    この状態の計算は、0-1 ナップサックにおける「選ぶか、選ばないか」という 1 回の比較を表しています。

3.   ナップサック容量を更新する順序

0-1 ナップサックに、重さ 2、価値 5 の品物が 1 つだけあり、ナップサックの容量は 4 です。 各品物は 1 回までしか選べません。最初の一次元配列は dp = [0, 0, 0, 0, 0] です。

ある生徒は、この品物を処理するとき、容量を 2 から 4 の順で更新しました。

  • dp[2] を更新すると 5 になる。
  • dp[3] を更新しても 5 になる。
  • dp[4] を更新するとき、更新したばかりの dp[2] を使うため、dp[4] = 10 になる。
  1. dp[4] = 10 という結果は正しいですか？その理由も説明してください。
  2. 「各品物は 1 回までしか選べない」という条件に基づくと、dp[4] はいくつですか？
  3. 各品物を処理するとき、容量は大きいほうから小さいほうへ更新しますか、それとも小さいほうから大きいほうへ更新しますか？その順序によって、どのような問題を防げますか？
解答

  1. この結果は正しくありません。価値 10 は、この価値 5 の品物を 2 回入れたことに相当し、 「各品物は 1 回までしか選べない」という条件に反します。

  2. ナップサックへ入れられるのはこの品物 1 つだけなので、正しい dp[4] は 5 です。

  3. 容量は大きいほうから小さいほうへ、つまり 4、3、2 の順に更新します。 この順序なら、dp[c] の計算時に読み取る dp[c-2] は、現在の品物を処理する前の値のままなので、 同じ回の中で現在の品物を繰り返し使うことを防げます。

14.8.2   プログラミング演習

1.   階段を上る方法の数

n 段の階段があります。1 回に 1 段または 2 段だけ上ることができ、ちょうど n 段目に着かなければなりません。 異なる上り方が何通りあるかを求めてください。n >= 1 とし、それぞれの上り方は、各回に 1 段進むか 2 段進むかだけで区別します。 一次元の動的計画法の配列を使って求め、2 つの状態だけを残す空間最適化は、ここでは使わないでください。

解法のヒント
  1. i 段目へ到達する最後の一歩では、1 段または 2 段だけ上れます
  2. そのため、dp[i] = dp[i-1] + dp[i-2] となります
  3. まず n が 1 と 2 の場合を処理し、3 段目から表を埋めます

LeetCode

2.   0-1 ナップサック

同じ長さの配列 wgt と val が与えられます。i 番目の品物の重さは正の整数 wgt[i]、価値は 0 以上の整数 val[i] で、 ナップサックの容量 cap は 0 以上の整数です。各品物は 1 回までしか選べません。総重量が cap 以下という条件で、 ナップサックに入れられる最大の総価値を求めてください。一次元の動的計画法を使って実装してください。

解法のヒント
  1. 長さ cap + 1 の配列 dp を初期化します。dp[c] は、容量上限が c のときの最大価値を表します
  2. 品物 i を処理するとき、「選ばない」場合の dp[c] と、「選ぶ」場合の dp[c-wgt[i]] + val[i] を比較します
  3. 同じ回の中で現在の品物を繰り返し選ばないように、容量は必ず大きいほうから小さいほうへ更新します
ご意見、ご質問、ご提案があればぜひコメントしてください