Open4
【問題解決力を鍛える！ アルゴリズムとデータ構造】の読書メモ
occhi問題解決力を鍛える!アルゴリズムとデータ構造 (KS情報科学専門書)
occhi5章 動的計画法
ナップサック問題
品物が6個あり、それぞれ順番に並べると(weight, value) = {(2, 3), (1, 2), (3, 6), (2, 1), (1, 3), (5, 85)}となるとする。
- 77Pの図5.10の横軸と縦軸が何を指してるか理解できない
-
dp[i][w]でいうiが縦軸、wが横軸になっている。 - また、マス目の値は、そのマス目のiとwでの、価値の総和を表している。
-
dp[i][w]の定義は最初から数えてi個の品物{0, 1, ....., i-1}までの中から重さがwを超えないように選んだときの価値の総和の最大値なので、i = 2かつw=15でも価値の総和が5になっていたりする。
-
- P77の赤マスと青マスの理解が難しかったので、以下に理解を残しておく。
- どちらも前までの状態から一つ品物を選んだ場合の価値を表している。
chmax(dp[i+1][w], dp[i][w - weight[i]] + value[i])
- 赤マス
-
dp[5][4] = 9の状態から、6つ目の品物((weight, value) = (5,85))を選んでいる。-
w = 4->w = 4 + 5となり、valueに関してはdp[6][9] = 9 + 85 = 94となる。
-
-
- 青マス
- 2個目と3個目の品物を選んだ状態が
dp[3][4] = 8となっており、その状態から1個目の品物を選ぶことによって、価値が11になっている。-
dp[3][4] = 8の状態から、dp[4][6] = 11になっている。
-
- 2個目と3個目の品物を選んだ状態が
- どちらも前までの状態から一つ品物を選んだ場合の価値を表している。
編集距離
- Frog問題と考え方は同じだ。
- いくつかの一個前の状態から、そのままにする・変更・挿入・削除をするの4通りの処理の中から、操作回数が最小となるものを、
dp[i][j]としている。-
dp[i-1][j]だと、文字Sの最初からi-1文字分と、Tの最初からj文字分との間の最短の編集距離。-
dp[i][j]への遷移に関して、Sのi文字目の対応が削除で済む場合だと、これに変更回数+1すれば良くなる。
-
-
dp[i-1][j-1]だと、文字Sの最初からi-1文字分と、Tの最初からj-1文字分との間の最短の編集距離。-
dp[i][j]への遷移に関して、Sのi文字目・Tのj文字目の対応が、変更（Sのi文字目=Tのj文字目にする）で済む場合だと、これに変更回数+1すれば良くなる。 - 変更が必要なく、そのままでいい場合だと、
dp[i][j] = dp[i-1][j-1]となる。
-
-
dp[i][j-1]だと、文字Sの最初からi文字分と、Tの最初からj-1文字分との間の最短の編集距離。-
dp[i][j]への遷移に関して、Tのj文字目の対応が削除で済む場合だと、これに変更回数+1すれば良くなる。
-
-
occhiここのナップザック問題だが、
一度重さWの制約を考えずに、
N個の品物があって、その中でいくつか選んで価値の最大値を求めると言う問題を考えると良い。
そうすると、dp[i]のような配列を用いて答えが求められることがわかる。
今回の問題は、上記の問題に変数Wを追加しただけなのである。と考えると、二次元配列を用いる理由がわかる。
occhiあかん、むずかしすぎる。、、、、
一旦以下の本を読んだ後にやろう。
以下の本だと、動的計画法や二分探索、貪欲法も網羅してくれてるみたいだし。
この本終わったら8章のデータ構造から再開しよう。