読書

動的計画法part4(個数制限なしナップサック問題)

問題概要 重さと価値がそれぞれWi,Viであるようなn種類の品物がある。 これらの品物から重さの総和がWを超えないように選んだときの、 価値の総和の最大を求めろ。 ただし、同じ種類の品物を使ってよい。i番目までの品物から重さの総和がj以下となるように選…

動的計画法part3(最長共通部分列問題)

問題概要 2つの文字列t, sが与えられる。 これら2つの共通部分文字列の長さの最大値を求めよ。 共通部分文字列とは、互いに共有する文字列であり、連続で一致している必要は無いが、 順序は等しくなければならない。 例示 s = "abcd" t = "becd"LCS = 3 (…

動的計画法part2(フィボナッチ数列)

問題概要 フィボナッチ数列の総和を返す 解法 1.メモ化 /* メモfb[]はあらかじめ-1(メモ無し)で初期化する */ fib(int a){ /* メモ化チェック */ if(fb[a] != -1 ) return fb[a]; if( a == 0 ) ret = 0; else if( a == 1 ) ret = 1; else ret = fib(a-1) + f…

動的計画法part1(ナップザック問題)

問題概要 重さwと価値vがついた品物がn個ある。 これらの品物から、重さの総和がWを超えないように選んだときの 価値の総和の最大値を求めなさい。 問題解法 1.全探索 再帰的に、品物をチェックし入れた場合、入れなかった場合とで探索を繰り返す。 重さの総…

FenceRepair

問題概要 とても長い板からN個の板を切り出す。 切り出す板はL1,L2,...Lnであり、元の板の合計となっている。 板を切断する際に、その板の長さだけコストがかかる。 例えば21の板を13と8に分けた場合、コストは13+8である。 最小コストで板を切り出した…

辞書最小の問題

問題概要 入力:N文字の文字列S、長さ0の文字列T 以下の操作を行い、辞書順比較でできるだけ小さい文字列Tを作れ。 ・Sの先頭を1文字削除し、Tの末尾に追加 ・Sの末尾を1文字削除し、Tの末尾に追加 問題考察 貪欲法を使う。 先頭の文字が小さければ小さい…

三角形作れるか問題

問題概要 入力として与えられる辺の候補より、周長が最も長い三角形を作れ 入力:辺の長さ 出力:周長 ただし、三角形を作ることができなければ0を出力せよ。 基礎知識 三角形が作れる条件は、 \[ 三角形で一番長い辺 方法 あらかじめ辺の配列を長い順にソ…

プログラマの数学

尊敬する結城先生の著書で覚えておきたいことをまとめる。 論理(AならばB) AならBは以下のように記述する。 \[ A \Rightarrow B \] 「AならばB」の定義は以下の通りである。 A B A▶︎B ture true ture ture false false false ture true false false true