Boxes and Candies（貪欲法）

貪欲法

貪欲法 とは、$ N $ ステップからなる意思決定問題において、ある特定のルールに基づいて その場での最善の選択 を繰り返していくアルゴリズムです。

問題

$ N $ 個の箱が一列に並んでおり、左から $ i $ 番目の箱には $ a_i $ 個のキャンディーが入っています。

次の操作を何回でも行うことができます。

🔹 キャンディーが１個以上入っている箱を１つ選び、その箱のキャンディを１個食べる。

この操作を何回か行うことで、「どの隣り合う２つの箱についても、それらの箱に入っているキャンディの個数の総和が $ x $ 以下である」という状態にしたいと考えています。

これを達成するために必要な 最小の操作回数 を求めて下さい。

解法・ソースコード

まず、左端の箱に注目してみます。

$ a_0 + a_1 \leqq x $ である場合は、$ a_0 $ を減らす必要はありません。

そして $ a_0 + a_1 > x $ であっても $ a_0 \leqq x $ である限りは $ a_0 $ を減らす必要はあります。

なぜなら $ a_0 $ を減らすよりは $ a_1 $ を減らした法が、$ a_2 $ のことを考えても得だからです。

以上をまとめると次のようにすればよいことが分かります。

🔹 $ a_0 > x $ ならば、$ a_0 = x $ とする。
🔹 各 $ i = 0, 1, …, N - 2 $ に対して、$ a_i + a_{i + 1} > x $ ならば $ a_{i} + a_{i + 1} - 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
#--------- 入力例 ----------
x = 3
lst = [2, 2, 2]
#---------------------------
n = len(lst)    # 箱の個数

res = 0         # 解（最小の操作回数）

# 先頭要素のみ x からの超過分を先に減らしておく。
if lst[0] > x:
    res += a[0] - x
    a[0] = x

# 左端から順に処理する
for i in range(n - 1):
    if lst[i] + lst[i + 1] > x:
        res += lst[i] + lst[i + 1] - x
        lst[i + 1] = x - lst[i]
print('【最終の状態（それぞれの箱に入っているキャンディの数）】')
print(lst)
print('------------------')
print('解（操作の最小回数）：', res)
【最終の状態（それぞれの箱に入っているキャンディの数）】

[2, 1, 2]

------------------

解（操作の最小回数）： 1

２番目の箱のキャンディを１個食べる方法が最適で、どの隣接する箱のキャンディの個数の総和も３となります。

したがって、最小の操作回数は１回です。

貪欲法のまとめ

貪欲法 の考え方をまとめます。

🔹 端から考えていき、後によいものを残す。
　（ $ a_0 $ はそのままに $ a_1 $ を減らした方が、後のことを考えるとよい）
🔹 交換しても悪化しない。
　（ $ a_0 $ の代わりに $ a_1 $ の方を減らしても、解が悪化することはない）