アルゴリズムと計算量の問題

文字列 $Z$ から $0$ 個以上の文字を取り除き、残った文字を元の順序のまま並べた文字列を、$Z$ の部分列という。$2$ つの文字列の両方の部分列になっている文字列を共通部分列という。

DNA の塩基配列を表す $2$ つの文字列
$$X=\mathrm{ACGTA},Y=\mathrm{CATGA}$$
について、$X$ の先頭 $i$ 文字と $Y$ の先頭 $j$ 文字の最長共通部分列の長さを $L[i][j]$ とする（$0\le i\le 5,0\le j\le 5$。$L[0][j]=L[i][0]=0$）。$X$ の $i$ 文字目を $x_i$、$Y$ の $j$ 文字目を $y_j$ とすると、$i,j\ge 1$ のとき
$$L[i][j]=\{\begin{array}{ll}L[i-1][j-1]+1& (x_i=y_j)\\ \max (L[i-1][j],L[i][j-1])& (x_i\ne y_j)\end{array}$$
が成り立つ。この漸化式で表を埋めて、$X$ と $Y$ の最長共通部分列の長さ $L[5][5]$ を求めよ。

文字列 $Z$ から $0$ 個以上の文字を取り除き、残った文字を元の順に並べて得られる文字列を $Z$ の部分列という（取り除く文字は連続していなくてよい）。$2$ つの文字列の両方の部分列であるものを共通部分列といい、共通部分列のうち長さが最大のものを最長共通部分列という。

$2$ つの DNA 塩基配列を表す文字列
$$X=\mathrm{GATCA},Y=\mathrm{TACGA}$$
の最長共通部分列の長さを求めよ。

文字列 $Z$ から $0$ 個以上の文字を取り除き、残った文字を元の順に並べて得られる文字列を、$Z$ の部分列という（取り除く文字は連続していなくてよい）。

$2$ つの文字列
$$X=\mathrm{DBACBAD},Y=\mathrm{ABDCADB}$$
を考える。$X$ と $Y$ がどちらも $Z$ の部分列となるような文字列 $Z$（$X$ と $Y$ の共通超列）のうち、長さが最小のものの長さを求めよ。

文字列 $X$ から $0$ 個以上の文字を取り除き、残った文字を順序を変えずに並べた文字列を $X$ の部分列という。$2$ つの文字列 $X,Y$ の両方の部分列である文字列を共通部分列といい、共通部分列のうち長さが最大のものを最長共通部分列という。

$$X=\mathrm{CABDAB},Y=\mathrm{ABCADB}$$

とする。$X$ と $Y$ の最長共通部分列は、文字列として何通りあるか求めよ。ただし、取り出す文字の位置が異なっても、文字列として同じものは $1$ 通りと数える。

次の $4$ 個の品物から、重さの合計が $8$ 以下になるようにいくつか選ぶ。各品物は選ぶか選ばないかのどちらかで、同じ品物を $2$ 個以上選ぶことはできない。

品物を A, B, C, D の順に $1,2,3,4$ 番目とし、$i$ 番目の品物の重さを $w_i$、価値を $v_i$ とする。$V[i][w]$ を「$1$ 番目から $i$ 番目までの品物だけを使い、重さの合計が $w$ 以下になるように選んだときの価値の合計の最大値」とすると、$V[0][w]=0$ であり、$i\geqq 1$ のとき
$$V[i][w]=\{\begin{array}{ll}V[i-1][w]& (w<w_i)\\ \max \left(V[i-1][w],V[i-1][w-w_i]+v_i\right)& (w\geqq w_i)\end{array}$$
が成り立つ。この表を $w=0,1,\dots ,8$ について埋め、選んだ品物の価値の合計の最大値 $V[4][8]$ を求めよ。