15.3.1
正確に証明しようとすると大変そうだけどRECURSIVE-MATRIX-CHAINの方が効率いい
15.3.2
マージソートは部分問題がほとんど重複しないので履歴管理しても意味ない。
15.3.3
最大化問題は実現できる。全ての部分構造最適性を最小と同じように示せる。
15.3.4
もし表に記録していないと仮定するとたとえばfi[i]を解くときもfi[i-1]を解くときもそれ以下、たとえばfi[2]の値などが必要になる。これが表に保存することで解消される。すなわちこれらが部分問題重複性
15.3.5
A1:10*3,A2:3*2,A3:2*3でやればよい
15.4.1
ノートに書いた
15.4.2
PRINT-LCS(X,i,j)
1 if i=0またはj=0
2 then return
3 if xi=yj
4 then PRINT-LCS(X,i-1,j-1)
5 print xi
6 else if c[i-1,j]>=c[i,j-1]
7 then PRINT-LCS(X,i-1,j)
8 else PRINT-LCS(X,i,j-1)
15.4.3
MEMOIZED-LCS-LENGTH(X,Y)
1 m ← length(X)
2 n ← length(Y)
3 for i ← 0 to m
4 for j ← 0 to n
5 do c[i,j] ← -1
6 return LOOKUP-LCS-LENGTH(X,Y,i,j)
LOOKUP-LCS-LENGTH(X,Y,m,n)
1 if c[i,j] >-1
2 then return c[i,j]
3 if i=0またはj=0
4 then c[i,j] ← 0
5 else if xi=yj
6 then c[i,j] ← LOOKUP-LCS-LENGTH(X,Y,i-1,j-1) + 1
7 else c[i,j] ← max[LOOKUP-LCS-LENGTH(X,Y,i-1,j), LOOKUP-LCS- LENGTH(X,Y,i,j-1)]
8 return c[i,j]
15.4.4
2行あればその2行で漸化式より事足りる。さらに2行なくても1行と３つの領域があれば実現可能
15.4.5
X=
15.5.1
履歴管理をつかってあとは漸化式の通りにかけばできる。
15.5.2
ノートに書いた
15.5.3
実行時間は漸近的には変化なし。使用記憶領域が減る
16.1.1
上をまねて履歴管理を使えばかける
実行時間はO(n^3)
16.1.2
集合Sと半開区間a=[si,fi)に対して逆の物を定義して後ろから証明
16.1.3
GREEDY-ACTIVITY-SELECTORをO(n)回使用して求める方法がある。これはO(n^2)
さらに、他の方法として
使用中の講義室と使用していない講義室のリストを作る
もし未使用リストに講義室があるならそれを利用
ないなら新たに講義室を追加
ソートにかかる実行時間がこの解法の実行時間である。すなわち、入力が小さければO(n),そうでなければO(nlgn)
16.1.4
ノートに書いた
16.2.1
貪欲法最適性と部分構造最適性を示せばよい
16.2.2
ｎ個のアイテムに対して重さWを1～Wまで繰り返す。
16.2.3
貪欲法使える
16.2.4
一番遠いガソリンスタンドを選んでいけばよい。m個ガソリンスタンドがあるとするならO(m)
16.2.6
全アイテムの重さの中央値を求める
中央値に対して ＜、＝、＞で三つの部分集合にわける。それぞれG,E,Lとする。
このときのそれぞれの集合の重さの合計をWg,We,Wlとする。
もしWg>Wなら集合Gの中の要素で再帰。
それ以外なら集合Gの要素をすべていれてもWにまだ余裕があることになる。このときの残りの容量はW-Wgである。
ここでEを追加する。
もし、Wg+We＞=WならEを取り除き終了。
そうでないなら、W-Wg-Weの容量に対して要素はLで再帰
以上より
T(n)<=T(n/2)+O(n) よって置き換え法より、T(n)=O(n)