応用情報技術者 2017年 秋期 午後 問03

解答の論理構成

1. 動的計画法の基本
   【問題文】では「元の容量制限以下の全ての値を容量制限としたときの、品物の種類を限定した問題（以下、小問題という）をあらかじめ解いておき、それらの解を用いる」方法を説明しています。既に「A, Bを選べる」行が完成しているので、ここを土台に「A, B, Cを選べる」行を埋めます。
2. 比較対象（Cを使わない場合）
   Cを導入しても選ばなければ価値はそのまま「A, Bを選べる」行の値です。容量制限2～5に対し、それぞれ「6」「8」「12」「14」が比較対象となります。
3. Cを使う場合の計算
   Cのパラメータは【問題文】で「容積が3で価値が9」と定義されています。容量制限 $t$ に対して C を最後に選ぶときの価値は
   価値 = 「A, B, Cを選べる」行の ( $t-3$ ) 列の価値 ＋ 9
   になります。
4. 容量ごとの最大値決定

1. 結論
   よって表4の空欄は
   ア = 6
   イ = 9
   ウ = 12
   エ = 15
   となります。

誤りやすいポイント

• 「容量制限 $t-3$ の値」を取る際に、うっかり上段（A, B 行）の値と足し合わせてしまうミスが多発します。必ず同じ行（A, B, C 行）の左側を参照します。
• Cを複数個入れられるかを考慮し忘れ、容量5で「9」で止めてしまうケースがあります。無制限個なので 3＋2 の組合せも検討し、最適値を再確認する必要があります。
• 既に完成している行の値をそのままコピーして終わりにしてしまうと、Cを使った場合のより高い価値を見落とします。

FAQ

解答の論理構成

1. 追加条件の確認
   問題文で「容積が3で価値が9である品物Cが追加」とあるので、既存の品物A（容積「1」・価値「2」）、品物B（容積「2」・価値「6」）に C（容積「3」・価値「9」）を加えた3種類で考えます。
2. A, B だけの場合の既知結果
   表4の2行目には「A, Bを選べる」ケースが完成済みで、容量制限「0～5」の価値合計は
   0→「0」、1→「2」、2→「6」、3→「8」、4→「12」、5→「14」
   であることが示されています。
3. C も選べる行の空欄を動的計画法で埋める
   箱を容量 t とし、C を最後に選ぶか否かで比較します（以下、表4の ア～エ を順に決定）。
   • t＝2：C（容積3）は入らない。よって既存値「6」を採用 ⇒ ア＝6
   • t＝3：
     ・C を使わない場合＝「8」
     ・C を使う場合＝容量 0 の値「0」＋C の価値「9」＝9
     大きい方は 9 ⇒ イ＝9
   • t＝4：
     ・使わない場合＝「12」
     ・使う場合＝容量1 の値「2」＋「9」＝11
     大きい方は 12 ⇒ ウ＝12
   • t＝5：
     ・使わない場合＝「14」
     ・使う場合＝容量2 の値「6」＋「9」＝15
     大きい方は 15 ⇒ エ＝15
4. 容量制限「5」での最終行は 15
   よって表4は
   0,1,2,3,4,5 → 0,2,6,9,12,15
   となります。最大価値合計は「15」。
5. 最後に選んだ品物を逆追跡
   問題文の手順に従い「最後に選んだ品物」をたどります。
   • t＝5 の値 15 は「C を最後に選んだ」結果なので、C を1個採用。残容量＝5−3＝2
   • t＝2 の値 6 は、表3の考え方より「B を最後に選んだ」結果なので、B を1個採用。残容量＝2−2＝0
   • 残容量 0 では「なし」。
6. 個数まとめ
   A は０個、B は1個、C は1個。模範解答と一致します。

誤りやすいポイント

• 比価値（価値／容積）が高い順に選ぶという“貪欲法”を適用すると「B を2個」（価値「12」）で止まり最大値を逃しがちです。
• 「一つの品物を選ぶ個数には制限がない」という条件を読み落とし、各種類1個ずつだと誤解するケース。
• 表を埋める際に「C を選ぶ場合は容量 t−3 の“同じ行”の値と足す」手順を忘れ、前行の値を参照してしまうミス。

FAQ

解答の論理構成

1. 変数 temp の計算 (オ)
   • 目的は「容量制限 t の状態に品物 s を追加した場合の価値合計」を求めることです。
   • 追加前の容量は t から「種類 s の品物の容量」を引いた残りなので、 【問題文】「sizes」を用いて t – sizes と表します。
   • よって オ ＝ t - sizes となります。
2. 最大価値合計の更新 (カ)
   • 比較に勝った temp を現在の小問題の解に採用します。
   • この解を保持する配列は【問題文】「maxvaluetは、容量制限tの小問題の価値合計を保持する配列」と明示されています。
   • 従って代入先は maxvaluet、つまり カ ＝ maxvaluet です。
3. 復元処理で参照する品物番号 (キ)
   • 復元ループでは「最後に選んだ品物」の配列を逆追跡します。
   • 【問題文】「choicetは…最後に選んだ品物を保持するための配列」とあるので、 現在の容量 k に対して参照すべき添字は choicek。
   • したがって キ ＝ choicek です。
4. 価値合計の最終出力 (ク)
   • ループ後、最終的な最適価値は「容量制限 V の小問題の解」に等しいです。
   • 【問題文】「maxvaluetは…価値合計を保持する配列」なので、 ク ＝ maxvalueV となります。

誤りやすいポイント

• t - sizes と t + sizes の取り違え
  「残り容量」を求める場面で加算してしまうと配列範囲外アクセスになります。
• 更新配列を temp や別作業用配列にしてしまう
  DP 表をひとつにまとめているため、正しくは maxvaluet を上書きします。
• 復元時に size[choicek] ではなく sizek と書いてしまう
  配列 size の添字は「品物番号」であって容量値ではありません。
• 最終出力を maxvaluek や temp にしてしまう
  復元ループ終了後の k は 0 とは限らず、最適値は常に maxvalueV に残っています。

FAQ

解答の論理構成

1. 計算量を決めるのは、図1に示された二重ループ部分です。問題文には
   「for(sを0からN−1まで1ずつ増やす)
   　　for(tをsizesからVまで1ずつ増やす)」
   と明記されています。
2. 外側の s ループは品物の種類数だけ回りますから回数は N 回になります。
3. 内側の t ループは、sizes 以上 V 以下を1ずつ進むので最悪でも V 回です。
4. よって、総反復回数は N × V。ビッグオー表記で
   「動的計画法を用いてナップザック問題を解く場合の計算量のオーダは、品物の種類の数をN、ナップザックの容量制限をVとすると、O(ケ)」
   とある ケ には NV を入れるのが妥当です。

誤りやすいポイント

• 「全探索＝指数時間」と早合点して $O(2^N)$ と書いてしまう。動的計画法は指数時間ではなく多項式時間で動く点を見落としがちです。
• 内側ループが sizes から始まるため平均反復数を考えようとして計算量を小さく見積もる。オーダ評価では最大値（最悪ケース）を取るので V と置くのが原則です。
• 添字や変数名に惑わされ、N と V を逆に書いてしまう。

FAQ