跳到主要内容

名古屋工業大学 工学研究科 情報工学専攻 2019年度 計算機ソフトウェア（データ構造とアルゴリズム）

标签：

Author​

GPT-5.6 Sol, 祭音Myyura

Description​

ナップサック問題に関する次の (1)、(2) の問いに答えよ。ただし、同一のアイテムを二つ以上収納することはできないものとする。また、ナップサックに収納可能な重さの総和を容量と呼ぶ。

(1)​

三つのアイテム A、B、C の重さをそれぞれ 2,3,12,3,1、価値をそれぞれ 5,7,35,7,3 とする。表 1 は、各列をナップサックに収納可能な容量、各行を収納するアイテムの候補とし、それぞれの設定における価値の総和の最大値を記載したものである。空欄 (a) から (c) に入るべき数値を答えよ。

アイテム \ 容量012345
アイテムなし000000
アイテム A のみ005555
アイテム A と B00(a)7712
アイテム A と B と C0358(b)(c)

(2)​

次の疑似コードは、容量 Wmax⁡W_{\max} に対して、nn 個 (n≥1)(n\geq1) のアイテムの重さを格納した配列 w[0…n−1]w[0\ldots n-1] と価値を格納した配列 v[0…n−1]v[0\ldots n-1] が与えられたときに、ナップサック問題を解くアルゴリズムである。二次元配列 M[0…n,0…Wmax⁡]M[0\ldots n,0\ldots W_{\max}] は (1) の表 1 に対応するものであり、要素 M[i,j]M[i,j] には、配列 w,vw,v の添字順に前から ii 個のアイテムを容量 jj で詰めた場合の価値の総和の最大値が計算される。

M[0...n, 0...W_max] を用意する
j = 0,...,W_max に対して M[0,j] = 0,
i = 0,...,n に対して M[i,0] = 0 として初期化

for i = 1,...,n
    for j = 1,...,W_max
        if j < alpha
            M[i,j] = M[i-1,j]
        else
            M[i,j] = max(M[i-1,j], M[i-1,j-beta] + gamma)
        endif
    endfor
endfor

ここでは重さと容量は正の整数であると仮定し、max は二つの引数の最大値を返す。また、kk 番目のアイテムの重さと価値は w[k]w[k]、v[k]v[k] によって参照できるものとする。次の問いに答えよ。

  • (ア) このアルゴリズムのように、問題を小さな部分問題に分解し、小さな問題の解を利用しながら問題のサイズを徐々に大きくして解を求める設計法を、次から選べ。
(a) 貪欲法,(b) ブルートフォース探索,(c) クラスタリング,(d) 動的計画法,(e) ハッシング.\begin{array}{lll} \text{(a) 貪欲法},&\text{(b) ブルートフォース探索},&\text{(c) クラスタリング},\\ \text{(d) 動的計画法},&\text{(e) ハッシング}.& \end{array}
  • (イ) 空欄 α,β,γ\alpha,\beta,\gamma に入るコードを次からそれぞれ選べ。ただし、同じ選択肢を何度選んでもよい。
(a) i−1,(b) i,(c) v[i−1],(d) v[i],(e) w[i−1],(f) w[i],(g) M[i−1,j],(h) M[i,j−1].\begin{array}{llll} \text{(a) }i-1,&\text{(b) }i,&\text{(c) }v[i-1],&\text{(d) }v[i],\\ \text{(e) }w[i-1],&\text{(f) }w[i],&\text{(g) }M[i-1,j],&\text{(h) }M[i,j-1]. \end{array}
  • (ウ) この疑似コードの nn と Wmax⁡W_{\max} に関する計算量の漸近的評価として当てはまるものを、以下からすべて選べ。
(a) O(n+Wmax⁡),(b) Ω((log⁡n)Wmax⁡),(c) O(n2Wmax⁡),(d) Θ((log⁡n)Wmax⁡),(e) O(nWmax⁡).\begin{array}{lll} \text{(a) }O(n+W_{\max}),&\text{(b) }\Omega((\log n)W_{\max}),&\text{(c) }O(n^2W_{\max}),\\ \text{(d) }\Theta((\log n)W_{\max}),&\text{(e) }O(nW_{\max}).& \end{array}

Kai​

(1)​

各行を順に更新すると、完成した表は次のようになる。

アイテム \ 容量012345
アイテムなし000000
アイテム A のみ005555
アイテム A と B0057712
アイテム A と B と C03581012

例えば容量 4 では、B と C を選ぶと重さ 3+1=43+1=4、価値 7+3=107+3=10 となる。したがって、

(a)=5,(b)=10,(c)=12\boxed{(a)=5,\qquad(b)=10,\qquad(c)=12}

である。

(2)​

(ア)​

小さい部分問題の解を表に保存して再利用しているので、

(d) 動的計画法\boxed{\text{(d) 動的計画法}}

である。

(イ)​

ループの ii は「先頭から ii 個」を表すため、今回追加するアイテムの添字は i−1i-1 である。その重さを w[i−1]w[i-1]、価値を v[i−1]v[i-1] とすると、遷移は

M[i,j]={M[i−1,j],j<w[i−1],max⁡{M[i−1,j], M[i−1,j−w[i−1]]+v[i−1]},j≥w[i−1]M[i,j]= \begin{cases} M[i-1,j],&j

となる。よって、

α=w[i−1] (e),β=w[i−1] (e),γ=v[i−1] (c)\boxed{\alpha=w[i-1]\ \text{(e)},\quad \beta=w[i-1]\ \text{(e)},\quad \gamma=v[i-1]\ \text{(c)}}

である。

(ウ)​

外側のループが nn 回、内側のループが Wmax⁡W_{\max} 回であり、各反復の処理は定数時間である。したがって計算量は

Θ(nWmax⁡)\Theta(nW_{\max})

である。これに対して成立する選択肢をすべて挙げると、n=Ω(log⁡n)n=\Omega(\log n) より (b)、nWmax⁡=O(n2Wmax⁡)nW_{\max}=O(n^2W_{\max}) より (c)、および最も直接的な上界 (e) である。したがって、

(b), (c), (e)\boxed{\text{(b), (c), (e)}}

となる。

検算​

一時プログラムで各アイテムについて全ての選択・非選択を列挙し、各容量の最適値と DP の全要素を比較した。両者は全行で一致し、最終表の各行はそれぞれ

[0, 0, 0, 0, 0, 0]
[0, 0, 5, 5, 5, 5]
[0, 0, 5, 7, 7, 12]
[0, 3, 5, 8, 10, 12]

となることを確認した。

本页目录