14.8   練習問題¶

14.8.1   知識の確認¶

1.   動的計画法に適した場面¶

ある生徒が「漸化式を書けるなら、必ず動的計画法を使うべきだ」と言いました。 次の各作業には、動的計画法、バックトラッキング、または dp 表を作らずループや数式を使う方法のどれがより適しているかを判断し、主な理由を一つ書いてください。

1. 額面 [1, 3, 4] の硬貨で金額 6 を作るための最少枚数を求めます。各硬貨は何枚でも使えます。
2. [1, 2, 3] の全順列を出力します。

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

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

2.   ナップサックの表の一マスを計算する¶

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] はいくつになりますか。どの品物を選ぶことに対応しますか。

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

0-1 ナップサック問題に、重さ 2、価値 5 の品物が一つだけあります。ナップサックの容量は 4 です。 各品物は一回だけ選べ、初期の一次元配列は 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. 「各品物は一回だけ選べる」という条件から、dp[4] はいくつになるべきですか。
3. 各品物を処理するとき、容量は大きい順と小さい順のどちらで更新すべきですか。その順序によって、どの問題を避けられますか。

14.8.2   プログラミング演習¶

1.   階段の上り方の数¶

n 段の階段があります。一回に 1 段か 2 段だけ上れ、ちょうど第 n 段に到達する必要があります。 異なる上り方が何通りあるかを計算してください。n >= 1 とし、各歩で 1 段進むか 2 段進むかによってのみ上り方を区別します。 一次元の動的計画法の配列を使い、二つの状態だけを残す空間最適化は、ここでは行わないでください。

LeetCode

2.   0-1 ナップサック問題¶

同じ長さの配列 wgt と val が与えられます。品物 i の重さは正の整数 wgt[i]、価値は非負整数 val[i] です。 ナップサックの容量 cap は非負整数です。各品物は一回だけ選べます。重さの合計が cap を超えない範囲で、 ナップサックに入れられる価値の合計の最大値を求めてください。一次元の動的計画法で実装してください。

コメント欄で、考えや質問、ご提案をお寄せください。