問題

N 個の品物があり、それぞれ 1 から N までの番号が付けれらています。

品物 i の重さは整数値 wi であり、価値は整数値 vi です。

いくつかの品物を選んで持ち帰りたいのですが、品物を入れるナップサックには容量制限があり、重さの合計が W 以下になるようにする必要があります。

価値の合計としてあり得る最大値はいくらになるでしょうか。

[制約]
🔹1≦N≦100
🔹1≦Wi≦100000
🔹1≦wi≦W
🔹1≦vi≦109

解き方・ソースコード

この問題は次の二次元配列に対して、動的計画法を適用して解くことができます。

🔹dp[i][j] ：品物１，２，…，N の中から、重さの合計が j となるように選ぶ。
　このとき、合計価値としてあり得る最大値はいくつになるか。

まず、i=0の場合は、何も選ぶことができませんので重さや価値の合計は必ず 0 になります。

dp[0][0]=0 とし、他の値については十分に大きなマイナスの値 −1015 を設定しておきます。

次に、i≧1 の場合は、dp[i][j] の状態になる方法、つまり品物 i までの中から重さの合計が j になるように選ぶ方法として以下の２つだけが考えられます。

🔹方法Ａ：品物 i−1 の時点で合計が j であり、品物 i を選ばない。
　　　➡　dp[i−1][j]
🔹方法Ｂ：品物 i−1 の時点で合計が j−wi であり、品物 i を選ぶ。
　　　➡　dp[i−1][j−wi]+vi

つまり dp[i][j] の値は、dp[i−1][j] と dp[i−1][j−wi]+vi のうち大きい方を選択します。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

#--------- 入力例 ----------
N = 4                       # 品物の数
W = 7                       # ナップサックに入れられる最大重量
w = [None, 3,  3,  5,  1]   # 各品物の重さ
v = [None, 13, 17, 29, 10]  # 各品物の価値
#---------------------------
# 動的計画法
dp = [[ -10 ** 15 ] * (W + 1) for i in range(N + 1)]
dp[0][0] = 0
for i in range(1, N + 1):       # 品物ごとにループ
    for j in range(0, W + 1):   # 重さごとにループ
        if j < w[i]:
            dp[i][j] = dp[i - 1][j]
        if j >= w[i]:
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i])

# 出力
print('解：', max(dp[N]))

注意が必要なのは、重さの合計がちょうど W のとき価値が最大になるとは限らないことです。

求める答えは dp[N][0],dp[N][1],…,dp[N][W] の最大値となります。

[実行結果]

解： 40

品物１、品物２，品物４を選んだ場合、重さの合計は[3 + 3 + 1 = 7]で価値の合計は[13 + 17 + 10 = 40]となりこれが価値の最大値となります。

問題

N 枚のカードが一列に並べられており、左から i 番目のカード（カード i とする）には整数 Ai が書かれています。

カードの中から何枚かを選んで、書かれた整数の合計が S となるときのカードの組み合わせを出力してください。

[制約]
🔹1≦N≦60
🔹1≦S≦10000
🔹1≦Ai≦10000

解き方・ソースコード

前回記事では、カードの合計値が S となるかどうかを判定しました。

今回はカードの合計値 S になる組み合わせがある場合、そのカードの組み合わせを出力します。

まずは、前回記事と同様に動的計画法を使って合計が S になるかどうかをチェックします。

この時に作成した dp を合計値 S から 0 にさかのぼって確認すると、選ぶべきカードを復元することができます。

カードを選ぶかどうかは、以下の２条件を確認することで判断します。

　🔹dp[x−1][合計値]=True の場合：カード x を選ばない
　🔹上記以外：カード x を選ぶ（カードを選んだら、カードの数字を合計値から差し引き、カード x を保管しておく）

　
[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

#--------- 入力例 ----------
N = 5
S = 7
A = [2, 1, 3, 8, 2]
#---------------------------
# 動的計画法（i=0）
dp = [[ None ] * (S + 1) for i in range(N + 1)]
dp[0][0] = True
for i in range(1, S + 1):
    dp[0][i] = False

# 動的計画法（i=1）
for i in range(1, N + 1):       # カードの枚数分ループ
    for j in range(0, S + 1):   # 0から合計値Sまでループ
        if dp[i - 1][j] or (j - A[i - 1] > -1 and dp[i - 1][j -A[i - 1]]):
            dp[i][j] = True
        else:
            dp[i][j] = False

# 答えの復元
Answer = []
Place = S
for i in reversed(range(1, N + 1)): # 合計値Sから、1までループ（今回の場合:5,4,3,2,1）
    if dp[i - 1][Place]:
        Place = Place - 0           # カード i を選ばない
    else:
        Place = Place - A[i - 1]    # カード i を選ぶ
        Answer.append(i)

# 答えを出力（インデックスよりカードに書かれた数字を出力）
print('解：', ' '.join(str(A[i - 1]) for i in reversed(Answer)))

[実行結果

解： 2 3 2

[2, 3, 2]という数字の書かれたカードの組み合わせを選ぶと、合計が7になることが分かりました😊

問題

N 枚のカードが一列に並べられており、左から i 番目のカード（カード i とする）には整数 Ai が書かれています。

カードの中から何枚かを選んで、書かれた整数の合計が S となるようにする方法があるかどうかを判定してください。

[制約]
🔹1≦N≦60
🔹1≦S≦10000
🔹1≦Ai≦10000

解き方・ソースコード

動的計画法を使うにあたり、以下のような２次元配列を用意します、

🔹dp[i][j]：カード１、カード２、…、カード iの中から何枚かを選び、選んだカードに書かれた整数の合計を j にすることが可能かどうか。

まず、i=0の場合は選んだカードの合計値が必ず0になるので、dp[0][0]を True に設定し、dp[0][1]以降を False に設定します。

i≧1の場合、dp[i][j]の状態になる方法つまりカード i までの中から合計が j になるように選ぶ方法としては次の２つの方法が考えられます。

🔹方法A：カードi−1 の時点で合計が j であり、カード i を選ばない。
🔹方法B；カードi−1 の時点で合計が j−Ai であり、カード i を選ぶ。

方法A・方法Bのうちどちらかが可能であれば、dp[i][j] の状態にすることができます。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#--------- 入力例1 ---------
N = 3
S = 7
A = [2, 2, 3]
#--------- 入力例2 ---------
# N = 3
# S = 6
# A = [2, 2, 3]
#---------------------------
# 動的計画法（i=0）
dp = [[ None ] * (S + 1) for i in range(N + 1)]
dp[0][0] = True
for i in range(1, S + 1):
    dp[0][i] = False

# 動的計画法（i=1）
for i in range(1, N + 1):       # カードの枚数分ループ
    for j in range(0, S + 1):   # 0から合計値Sまでループ
        if dp[i - 1][j] or (j - A[i - 1] > -1 and dp[i - 1][j - A[i - 1]]):
            dp[i][j] = True
        else:
            dp[i][j] = False

print('解：', 'Yes' if dp[N][S] else 'No')

[実行結果（入力例1）]

解： Yes

すべてのカードを選択すると[2 + 2 + 3 = 7]となり、正解はYesとなります。

[実行結果（入力例2）]

解： No

３枚のカードをどう組み合わせても6にはならないので、正解はNoとなります。

問題

N 個の足場があり、左から i 番目の足場（足場 i とする）の高さは hi です。

ウサギは以下の２種類の行動を繰り返すことで、足場１から足場 N に移動します。

　🔹足場 i−2 から足場 i に、コスト |hi−2−hi| かけて移動する。
　🔹足場 i−1 から足場 i に、コスト |hi−1−hi| かけて移動する。

足場 1 から足場 N に移動するのに、最短コストのルートを１つ出力して下さい。

解き方・ソースコード

前々回の記事では同じ問題の最短コストを求めましたが、今回は最短コストで移動する際のルート（経路）を求める問題となります。

この問題ではゴールから順番にスタートへの経路を考えることで解くことができます。

まずは、前々回記事と同様に動的計画法を使って最短コストを求めます。

この時に作成した dp を確認すると次のように最適解(最短コストとなるルート)を復元することができます。

　🔹dp[x]=dp[x−1]+|H[x−1]−H[x]| の場合：方法Aを選ぶ
　🔹dp[x]=dp[x−2]+|H[x−2]−H[x]| の場合：方法Bを選ぶ

なお、上の２つの条件両方を満たす場合は、方法A・方法Bどちらを選んでも構いません。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

#--------- 入力例 ----------
N = 6
H = [30, 10, 60, 10, 60, 50]
#---------------------------
# 配列の準備
dp = [ None ] * N

# 動的計画法
dp[0] = 0
#print('足場1までの最小コスト', dp)

dp[1] = abs(H[0] - H[1])
# print('足場2までの最小コスト', dp)

for i in range(2, N):   # 足場3以降の最小コスト
    dp[i] = min(dp[i - 1] + abs(H[i - 1] - H[i]), dp[i - 2] + abs(H[i - 2] - H[i]))
    # print('足場{}までの最小コスト'.format(i + 1), dp)

# 答えの復元
# 変数 Place は現在位置（ゴールからスタート地点へ向かう）
Answer = []
Place = N - 1
while True:
    Answer.append(Place)
    print(Answer)
    if Place == 0:
        break

    # どこから足場 Place に向かうのが最適かを求める
    if dp[Place - 1] + abs(H[Place - 1] - H[Place]) == dp[Place]:
        Place = Place - 1   # １つ前の足場に移動
    else:
        Place = Place - 2   # ２つ前の足場足場に移動

# 答えを出力(Answer[0]が足場１に対応)
print('解：', ' → '.join(str(i + 1) for i in reversed(Answer)))

[実行結果]

[5]

[5, 4]

[5, 4, 2]

[5, 4, 2, 0]

解： 1 → 3 → 5 → 6

最短コストにするためには1 → 3 → 5 → 6というルート（経路）であることが確認できました😊

問題

N 個の部屋があり、1 から N までの番号が付けられています。

この部屋はすべて一方通行であり、通路を介して１つ先または２つ先の部屋に移動できます。

各通路における移動時間は以下の通りです。

🔹部屋 i−1 から部屋 i に向かう通路を通るのに Ai 分 (2≦i≦N) かかる
🔹部屋 i−2 から部屋 i に向かう通路を通るのに Bi 分 (3≦i≦N) かかる

部屋 1 から部屋 N に移動するのに、最短時間のルートを１つ出力して下さい。

[制約]
🔹3≦n≦100000
🔹1≦Ai≦100(2≦i≦N)
🔹1≦Bi≦100(3≦i≦N)

解き方・ソースコード

前々回の記事では同じ問題の最短時間を求めましたが、今回は最短時間で移動する際のルート（経路）を求める問題となります。

この問題ではゴールから順番にスタートへの経路を考えることで解くことができます。

まずは、前々回記事と同様に動的計画法を使って最短時間を求めます。

この時に作成した dp を確認すると次のように最適解(最短時間となるルート)を求めることができます。

　🔹dp[x]=dp[x−1]+Ax の場合：方法Aを選ぶ
　🔹dp[x]=dp[x−2]+Bx の場合：方法Bを選ぶ

なお、上の２つの条件両方を満たす場合は、方法A・方法Bどちらを選んでも構いません。

最後に、復元した経路を逆順に並べ替えることにより、最短ルートを求めます。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

#--------- 入力例 ----------
N = 5
A = [2, 4, 1, 3]
B = [5, 3, 7]
#---------------------------
# 動的計画法
dp = [None] * (N + 1)
dp[1] = 0
dp[2] = A[0]
for i in range(3, N + 1):
    dp[i] = min(dp[i - 1] + A[i - 2], dp[i - 2] + B[i - 3])

# 答えの復元
# 変数 Place は現在位置（ゴールからスタート地点へ向かう）
Answer = []
Place = N
while True:
    Answer.append(Place)
    print(Answer)
    if Place == 1:
        break

    # どこから部屋 Place に向かうのが最適かを求める
    if dp[Place - 1] + A[Place - 2] == dp[Place]:
        Place = Place - 1   # １つ前の部屋に移動
    else:
        Place = Place - 2   # ２つ前の部屋に移動

# 答えを出力
print('解：', ' → '.join(str(i) for i in reversed(Answer)))

[実行結果(入力例1)]

[5]

[5, 4]

[5, 4, 2]

[5, 4, 2, 1]

解： 1 → 2 → 4 → 5

最短時間にするためには1 → 2 → 4 → 5という経路であることが確認できました😊

問題

N 個の足場があり、左から i 番目の足場（足場 i とする）の高さは hi です。

ウサギは以下の２種類の行動を繰り返すことで、足場１から足場 N に移動します。

　🔹足場 i−2 から足場 i に、コスト |hi−2−hi| かけて移動する。
　🔹足場 i−1 から足場 i に、コスト |hi−1−hi| かけて移動する。

移動にかかる合計コストの最小値を出力して下さい。

解き方・ソースコード

この問題は、足場１から足場 i までの最小コストを dp[i−1] とし、dp[0]→dp[1]→･･･→dp[N−1] の順に１つずつ計算すると、答えを出すことができます。

配列 dp の計算方法としては、まず足場１から足場１までは移動する必要がないので、dp[0]=0 となります。

次に足場１から足場２まで行くには直接移動するしかないので、dp[1]=h0−h1 となります。

dp[2] 以降は最後の行動で場合分けをして考えます。足場 i まで移動するには、次の２つが考えられます。

　（方法１）足場 i−1 まで移動した後、１つ隣りの足場 i に行く。
　（方法２）足場 i−2 まで移動した後、２つ隣りの足場 i に行く。

ここで、方法１を選んだ時の合計コストは dp[i−1]+abs(H[i−1]−H[i]) であり、方法２を選んだ時の合計コストは dp[i−2]+abs(H[i−2]−H[i]) です。

コストの少ないほうを求める問題なので、dp[i] の値は次式のように表すことができます。

dp[i]=min(dp[i−1]+abs(H[i−1]−H[i]),dp[i−2]+abs(H[i−2]−H[i]))

上記の内容を踏まえてコーディングすると下記のようなソースコードになります。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

#--------- 入力例 ----------
N = 6
H = [30, 10, 60, 10, 60, 50]
#---------------------------
# 配列の準備
dp = [ None ] * N

# 動的計画法
dp[0] = 0
print('足場1までの最小コスト', dp)

dp[1] = abs(H[0] - H[1])
print('足場2までの最小コスト', dp)

for i in range(2, N):   # 足場3以降の最小コスト
    dp[i] = min(dp[i - 1] + abs(H[i - 1] - H[i]), dp[i - 2] + abs(H[i - 2] - H[i]))
    print('足場{}までの最小コスト'.format(i + 1), dp)

# 出力
print('解：', dp[N - 1])

[実行結果(入力例1)]

足場1までの最小コスト [0, None, None, None, None, None]

足場2までの最小コスト [0, 20, None, None, None, None]

足場3までの最小コスト [0, 20, 30, None, None, None]

足場4までの最小コスト [0, 20, 30, 20, None, None]

足場5までの最小コスト [0, 20, 30, 20, 30, None]

足場6までの最小コスト [0, 20, 30, 20, 30, 40]

解： 40

足場１→足場３→足場５→足場６と移動すると最小コスト40で移動することができます。

問題

N 個の部屋があり、1 から N までの番号が付けられています。

この部屋はすべて一方通行であり、通路を介して１つ先または２つ先の部屋に移動できます。

各通路における移動時間は以下の通りです。

🔹部屋 i−1 から部屋 i に向かう通路を通るのに Ai 分 (2≦i≦N) かかる
🔹部屋 i−2 から部屋 i に向かう通路を通るのに Bi 分 (3≦i≦N) かかる

部屋 1 から部屋 N に移動するのに、最短何分かかるでしょうか。

[制約]
🔹3≦n≦100000
🔹1≦Ai≦100　(2≦i≦N)
🔹1≦Bi≦100　(3≦i≦N)

解き方・ソースコード

この問題は、部屋１から部屋 i までの最短時間を dp[i] とし、dp[1]→dp[2]→･･･→dp[N] の順に１つずつ計算すると、答えを出すことができます。

配列 dp の計算方法としては、まず部屋１から部屋１までは移動する必要がないので、dp[1]=0 となります。

次に部屋１から部屋２まで行くには直接移動するしかないので、dp[2]=A2 となります。

dp[3] 以降は最後の行動で場合分けをして考えます。部屋 i まで移動するには、次の２つが考えられます。

　（方法１）部屋 i−1 まで移動した後、１本の通路を通って部屋 i に行く。
　（方法２）部屋 i−2 まで移動した後、１本の通路を通って部屋 i に行く。

ここで、方法１を選んだ時の合計時間は dp[i−1] 分であり、方法２を選んだ時の合計時間は dp[i−2] 分です。

時間の短いほうを求める問題なので、dp[i] の値は次式のように表すことができます。

dp[i]=min(dp[i−1]+Ai,dp[i−2]+Bi)

上記の内容を踏まえてコーディングすると下記のようなソースコードになります。

A, B が 0 番目から始まっていることに注意して下さい。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

#--------- 入力例 ----------
N = 5
A = [2, 4, 1, 3]
B = [5, 3, 7]
#---------------------------
# 動的計画法
dp = [ None ] * (N + 1)

dp[1] = 0       # 部屋1までの最短時間
print('部屋1番目までの最短時間', dp)

dp[2] = A[0]    # 部屋2までの最短時間
print('部屋2番目までの最短時間', dp)

for i in range(3, N + 1):
    dp[i] = min(dp[i - 1] + A[i - 2], dp[i - 2] + B[i - 3])
    print('部屋{}番目までの最短時間'.format(i), dp)
# 出力
print('解：', dp[N])

[実行結果]

部屋1番目までの最短時間 [None, 0, None, None, None, None]

部屋2番目までの最短時間 [None, 0, 2, None, None, None]

部屋3番目までの最短時間 [None, 0, 2, 5, None, None]

部屋4番目までの最短時間 [None, 0, 2, 5, 5, None]

部屋5番目までの最短時間 [None, 0, 2, 5, 5, 8]

解： 8

部屋1から部屋5までの最短時間が8分であることを導き出すことができました😊

問題

黒板に0という整数が書かれています。

その整数に対して N 回の操作を行います。

i回目の操作は文字Tiと整数Aiで表され、その操作内容は次の３種類です。

🔹Ti=+ のとき：Ai を足す。
🔹Ti=− のとき：Ai を引く。
🔹Ti=∗ のとき：Ai を掛ける。

各操作が終わった後について、黒板に書かれた整数を10000で割った余りを出力するプログラムを作成して下さい。

[制約]
🔹1≦n≦100000
🔹1≦Ai≦100
🔹黒板に書かれる整数は常に0以上

解き方・ソースコード

この問題はオーバーフローを防ぐために操作が行われるたびに余りをとるということがポイントとなります。

ただし引き算を行う場合、計算結果がマイナスになってしまう可能性がるため、計算の途中で0を下回った場合10000を足す必要があります。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

#--------- 入力例1 ----------
N = 4
A = ['+ 59',
     '+ 41',
     '* 100',
     '- 1']
#----------------------------
# 現在の黒板の数
Answer = 0
for a in A:
    ss = a.split()
    if ss[0] == '+':
        Answer += int(ss[1])
    elif ss[0] == '-':
        Answer -= int(ss[1])
    elif ss[0] == '*':
        Answer *= int(ss[1])

    # 引き算で答えが 0 未満になった場合
    if Answer < 0:
        Answer += 10000

    # 余りをとる
    Answer %= 10000
    print(Answer)

[実行結果(入力例1)]

59
100
0
9999

解が非常に大きくなる問題では、余りを出力するということがよくあるので上記の手法を覚えておくことはとても有益です。

問題

N 個の商品があり、商品 i(1≦i≦N)の価格は Ai 円です。

異なる３つの商品を選び、合計価格をちょうど1000円にすることができるでしょうか。

答えをYesかNoで出力して下さい。

[制約]
🔹3≦n≦100

解き方・ソースコード

この問題は３重ループを使うことで解くことができます。

１つめのループは全商品をチェックするために、N 回実行します。

２つめのループは１つめの商品と同じ商品を選ばないように、N−1 回実行します。

３つめのループは１つめ、２つめの商品と同じ商品を選ばないように、N−2 回実行します。

３重ループの中では、選んだ３つの商品の合計が1000円かどうかを確認します。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

#--------- 入力例1 ----------
N = 3
A = [200, 300, 400]
#--------- 入力例2 ----------
# N = 5
# A = [100, 200, 300, 400, 500]
#----------------------------
def check(n, a):
    for i in range(n):
        for j in range(i + 1, n):
            for k in range(j + 1, n):
                if a[i] + a[j] + a[k] == 1000:
                    return "Yes"
    else:
        return "No"

print(check(N, A))

[実行結果(入力例1)]

No

与えられた３つの価格では1000円になることはないので、解はNoとなります。

[実行結果(入力例2)]

Yes

与えられた５つの価格のうち、[100, 400, 500]を選択すると1000円になりますので、解はYesとなります。

Bokeh

PyScript内から、Bokehを使って折れ線グラフを表示します。

まずBokenライブラリを使うため、headタグに下記のようにCDN（コンテンツ配信ネットワーク）を設定します。

1

<script type="text/javascript" src="https://cdn.bokeh.org/bokeh/release/bokeh-2.4.2.min.js"></script>

次にpy-configタグにbokehとnumpyを指定します。

そしてpy-script内では、Bokeh関連ライブラリをいろいろとインポートし、その後でBokenライブラリを使って図形オブジェクトを作成します。

最後にjson.dumps関数とBokeh.embed.embed_item関数を使ってブラウザ上に折れ線グラフを表示します。

（ざっくりとした説明になってしまいましたが、詳しくは下記のサンプルコードをご参照ください🙇‍♂️）

[ソースコード]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

<html>
  <head>
    <script type="text/javascript" src="https://cdn.bokeh.org/bokeh/release/bokeh-2.4.2.min.js"></script>

    <link rel="stylesheet" href="https://pyscript.net/latest/pyscript.css" />
    <script defer src="https://pyscript.net/latest/pyscript.js"></script>
  </head>

  <body>
    <div id="mpl"></div>

    <py-config>
      packages = ["bokeh", "numpy"]
    </py-config>

    <py-script>
      import json
      import pyodide

      from js import Bokeh, console, JSON

      from bokeh.embed import json_item
      from bokeh.plotting import figure
      from bokeh.resources import CDN

      d = [0, 1, 4, 9, 16]
      p = figure()
      p.line(range(len(d)), d) #     第1引数がx軸、第2引数がy軸

      p_json = json.dumps(json_item(p, "mpl"))  # pは図形オブジェクトで、"mpl"はHtml上のDiv-IDを指定
      Bokeh.embed.embed_item(JSON.parse(p_json))

    </py-script>

  </body>
</html>

[ブラウザ表示]

PyScript内で作成したBokehの図形オブジェクトを、ブラウザ上で表示することができました😊