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

次の $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$）。漸化式
$$V[i][w]=\max (V[i-1][w],V[i-1][w-w_i]+v_i)$$
（ただし $w<w_i$ のときは $V[i][w]=V[i-1][w]$）を用いて表を埋め、選んだ品物の価値の合計の最大値 $V[4][8]$ を求めてください。

次の $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$）。

$$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\ge w_i)\end{array}$$

を使って表を埋め、重さの合計が $8$ 以下のときの価値の合計の最大値 $V[4][8]$ を求めてください。

次の $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]$ を求めよ。

$8$ 種類の文字 $\mathrm{A},\mathrm{B},\mathrm{C},\mathrm{D},\mathrm{E},\mathrm{F},\mathrm{G},\mathrm{H}$ からなる長さ $100$ の文字列があり、各文字の出現回数は次の表のとおりである。

各文字に、$3$ 種類の記号 $0,1,2$ からなる長さ $1$ 以上の符号語を $1$ つずつ割り当てる。ただし、異なる文字の符号語は異なり、どの符号語も他の符号語の先頭部分（接頭語）になっていない（語頭符号である）ものとする。文字列の各文字をその符号語に置きかえてつなげたとき、得られる記号列の長さ（記号の個数）の最小値を求めよ。

互いに異なる $8$ 個の実数を並べた配列 $A[1],A[2],\dots ,A[8]$ の最大値と最小値を、次のアルゴリズムで同時に求める。

• 最初に $M\leftarrow A[1]$, $m\leftarrow A[1]$ とする。
• $i=2,3,\dots ,8$ の順に、次の操作を行う。
• まず $A[i]$ と $M$ を比較する。$A[i]>M$ ならば $M\leftarrow A[i]$ とし、この $i$ についての操作を終える（$m$ とは比較しない）。
• $A[i]<M$ ならば、続けて $A[i]$ と $m$ を比較する。$A[i]<m$ ならば $m\leftarrow A[i]$ とする。

配列の並び方は $8!$ 通りのどれも同様に確からしいとする。このアルゴリズムで行われる要素どうしの比較（$A[i]$ と $M$ の比較、$A[i]$ と $m$ の比較）の回数の期待値を求めよ。