問１６：連立一次方程式（ガウスの消去法）
連立一次方程式を解くアルゴリズムには様々なものがあるが、その中で「ガウスの消去法」について調べ、そのアルゴリズムを説明しなさい。また、次の連立方程式をガウスの消去法で解くプログラムを作成しなさい。ただし、Sympy, Numpy.ligalg, Scipy.ligalg は使わないこと（答え合わせに使うのは良い）。また、参考に用いた書籍またはウェブサイトがある場合はそれを明記すること。
$3 x_1 + 2 x_2 + 7 x_3 + x_4 = 8$
$x_1 + 5 x_2 + x_3 - x_4 = 5$
$4 x_1 + x_2 + 3 x_3 - 2 x_4 = 7$
$x_1 + 6 x_2 + 4 x_3 + 3 x_4 = 13$
問１７：連立一次方程式（ヤコブ法）→すみません、解けませんので問題取り消します
連立一次方程式を解くアルゴリズムには様々なものがあるが、その中で「ヤコブ法」について調べ、そのアルゴリズムを説明しなさい。また、次の連立方程式をヤコブ法で解くプログラムを作成しなさい。ただし、Sympy, Numpy.ligalg, Scipy.ligalg は使わないこと（答え合わせに使うのは良い）。参考に用いた書籍またはウェブサイトがある場合はそれを明記すること。
$3 x_1 + 2 x_2 + 7 x_3 + x_4 = 8$
$x_1 + 5 x_2 + x_3 - x_4 = 5$
$4 x_1 + x_2 + 3 x_3 - 2 x_4 = 7$
$x_1 + 6 x_2 + 4 x_3 + 3 x_4 = 13$
問１８：ナップサック問題
重さが $W_i$、価値が $V_i$ である $n$ 個のアイテムがあります。これらの中から、重さの和が $x$ を超えない範囲内でアイテムを選んだときの、価値の和の最大値を求めなさい。
ただし、同じアイテムは１個しか選べないものとし、
- 1 ≤ $n$ ≤ 100
- 1 ≤ $W_i$ ≤ 100
- 1 ≤ $V_i$ ≤ 100
- 10n ≤ $x$ ≤ 100n
とする。
【ヒント】 「動的計画法」で解ける問題として典型的なものです。「再帰」を使って解けます。単純な探索では、同じ計算を繰り返して無駄な時間を使ってしまいます。これを避けるため、計算結果を格納する２次元配列を作って記憶することで、２度目以降の計算を省略するようにしてみましょう。
例18-1
n = 5
x = 175
W = [95, 56, 65, 54, 32]
V = [79, 9, 57, 55, 27]
139
例18-2
n = 10
x = 492
W = [53, 64, 82, 93, 76, 67, 10, 6, 82, 91]
V = [80, 16, 30, 68, 31, 19, 50, 64, 20, 96]
438
例18-3
n = 20
x = 1371
W = [30, 31, 100, 83, 52, 97, 34, 70, 96, 13, 70, 89, 79, 51, 31, 93, 73, 10, 77, 31]
V = [31, 58, 49, 75, 1, 57, 8, 1, 35, 22, 82, 28, 61, 46, 68, 10, 32, 84, 19, 16]
783
例18-4
n = 40
x = 2250
W = [96, 64, 21, 86, 49, 72, 4, 90, 91, 91, 43, 95, 89, 23, 38, 58, 29, 43, 27, 3, 47, 29, 5, 90, 46, 100, 94, 56, 49, 62, 46, 51, 41, 28, 47, 61, 28, 100, 91, 80]
V = [74, 83, 57, 64, 63, 58, 100, 59, 66, 66, 85, 55, 86, 25, 41, 64, 26, 1, 87, 88, 73, 98, 57, 63, 31, 69, 21, 79, 96, 13, 2, 50, 89, 10, 11, 93, 45, 31, 15, 67]
2260
例18-5
n = 80
x = 2685
W = [7, 32, 92, 96, 96, 77, 49, 84, 80, 22, 14, 87, 4, 61, 27, 90, 23, 98, 59, 80, 25, 45, 14, 46, 41, 72, 86, 40, 27, 97, 96, 52, 86, 85, 55, 48, 92, 69, 57, 89, 2, 63, 20, 80, 98, 85, 31, 86, 65, 87, 94, 27, 95, 43, 27, 24, 65, 9, 81, 53, 36, 43, 14, 98, 85, 9, 66, 45, 49, 10, 68, 19, 5, 61, 53, 76, 75, 75, 55, 36]
V = [71, 6, 45, 90, 41, 89, 5, 57, 19, 78, 79, 100, 9, 45, 84, 41, 90, 18, 100, 34, 60, 6, 7, 82, 64, 40, 17, 44, 85, 94, 33, 90, 36, 50, 46, 66, 6, 57, 36, 4, 15, 50, 23, 94, 99, 26, 33, 95, 16, 45, 6, 93, 37, 89, 13, 52, 4, 92, 86, 10, 41, 12, 85, 43, 98, 92, 57, 38, 75, 61, 66, 1, 74, 61, 91, 33, 35, 96, 13, 17]
3594
例18-6
n = 100
x = 1913
W = [17, 22, 91, 12, 12, 76, 56, 86, 63, 42, 26, 15, 8, 11, 99, 60, 30, 90, 35, 92, 10, 49, 39, 58, 60, 80, 28, 9, 47, 43, 87, 55, 54, 46, 33, 50, 67, 52, 2, 51, 6, 50, 1, 83, 64, 58, 47, 63, 99, 6, 65, 17, 11, 99, 94, 23, 75, 8, 87, 44, 40, 53, 60, 69, 2, 74, 73, 44, 77, 21, 30, 51, 50, 63, 64, 21, 72, 6, 28, 19, 78, 38, 71, 68, 84, 92, 60, 34, 63, 17, 86, 22, 79, 48, 98, 40, 39, 41, 72, 30]
V = [47, 44, 4, 11, 94, 44, 20, 2, 61, 59, 31, 20, 87, 18, 16, 79, 2, 2, 58, 31, 67, 35, 19, 39, 30, 15, 63, 31, 70, 13, 35, 50, 20, 18, 6, 8, 49, 13, 44, 60, 65, 5, 51, 15, 84, 74, 50, 34, 35, 91, 97, 18, 54, 27, 3, 29, 86, 44, 74, 94, 85, 75, 92, 66, 83, 34, 63, 74, 8, 62, 25, 68, 45, 59, 28, 54, 75, 98, 8, 35, 98, 42, 22, 51, 48, 43, 29, 73, 68, 41, 78, 62, 61, 4, 44, 91, 10, 35, 22, 51]
3388
参考：例の作り方
import random
n = 10
x = random.randint(n * 10, n * 100)
W = [random.randint(1, 100) for _ in range(n)]
V = [random.randint(1, 100) for _ in range(n)]
問１９：最長共通部分列
長さ $n$ の文字列 $s$ と、長さ $m$ の文字列 $t$ を入力としたとき、その２つの文字列の最長共通部分列の長さを求める関数を作りなさい。
ただし、
- 1 ≤ $n$ ≤ 104
- 1 ≤ $m$ ≤ 104
とする。
【ヒント】 これも「動的計画法」で解けます。またこの解法は、生命情報学（バイオインフォマティクス」という分野で日常的に用いられる配列相同性検索の基礎となるものです。
例19-1
s = "pencil"
t = "penguin"
4
例19-2
s = "dreamingly"
t = "dreadfully"
6
例19-3
s = "This is a pen. This is an apple."
t = "pen-pineapple-apple-pen"
10
例19-4
s = "There is more to life than increasing its speed. "\
"(by Mahatma Gandhi)"
t = "There is always light behind the clouds. "\
"(by Louisa May Alcott)"
31
例19-5
s = "If you want to be successful, it's just this simple: "\
"Know what you are doing, love what you are doing, "\
"and believe in what you are doing. "\
"(by Will Rogers)"
t = "Success is not the key to happiness. "\
"Happiness is the key to success. "\
"If you love what you are doing, "\
"you will be successful. "\
"(by Louisa May Alcott)"
71
問２０：個数制限なしナップサック問題
重さが $W_i$、価値が $V_i$ である $n$ 個のアイテムがあります。これらの中から、重さの和が $x$ を超えない範囲内でアイテムを選んだときの、価値の和の最大値を求めなさい。
ただし、同じアイテムをいくつでも選べるものとし、
- 1 ≤ $n$ ≤ 100
- 1 ≤ $W_i$ ≤ 100
- 1 ≤ $V_i$ ≤ 100
- 1 ≤ $x$ ≤ 104
とする。
【ヒント】 「同じアイテムをいくつでも選べる」というだけで、問６よりも格段に難しくなります。「同じアイテムをいくつでも」をループとして表現してしまうと、計算量が大きくなりすぎるため避けたいところです。重さの上限が x という条件においてアイテム i を k 個選ぶという状況を、重さの上限が x - Wi という条件においてアイテム i を k - 1 個選ぶという状況と比較して考えます。
例20-1
n = 3
W = [3, 4, 2]
V = [4, 5, 3]
x = 7
10
例20-2
n = 10
x = 867
W = [28, 92, 30, 1, 40, 33, 96, 30, 38, 86]
V = [6, 77, 53, 91, 47, 33, 28, 28, 78, 36]
78897
例20-3
n = 20
x = 1272
W = [10, 87, 38, 74, 19, 93, 34, 24, 63, 12, 31, 99, 45, 4, 22, 81, 50, 75, 36, 20]
V = [1, 96, 33, 97, 58, 31, 68, 60, 23, 60, 27, 7, 24, 70, 60, 73, 11, 88, 87, 71]
22260
例20-4
n = 40
x = 3309
W = [20, 5, 85, 84, 10, 15, 80, 24, 48, 96, 33, 18, 22, 58, 62, 24, 12, 73, 76, 9, 53, 7, 47, 82, 69, 82, 57, 33, 60, 10, 84, 16, 97, 9, 57, 92, 22, 1, 70, 26]
V = [83, 17, 72, 71, 40, 16, 94, 78, 41, 43, 38, 21, 3, 35, 58, 59, 63, 75, 5, 64, 75, 30, 48, 45, 69, 7, 25, 37, 80, 70, 93, 68, 41, 34, 60, 39, 8, 86, 64, 27]
284574
例20-5
n = 40
x = 1747
W = [60, 76, 2, 14, 89, 88, 83, 27, 55, 10, 53, 58, 60, 45, 90, 73, 32, 54, 90, 97, 28, 54, 10, 70, 73, 61, 5, 14, 35, 65, 57, 12, 9, 85, 98, 51, 49, 13, 98, 16]
V = [23, 25, 14, 1, 39, 18, 16, 81, 67, 75, 14, 23, 95, 58, 47, 99, 33, 100, 9, 19, 57, 52, 36, 16, 30, 83, 99, 61, 97, 74, 16, 27, 70, 81, 84, 13, 28, 14, 12, 27]
34565
参考：例の作り方
import random
n = 40
x = random.randint(n * 10, n * 100)
W = [random.randint(1, 100) for _ in range(n)]
V = [random.randint(1, 100) for _ in range(n)]
print("n = ", n)
print("x = ", x)
print("W = ", W)
print("V = ", V)