最安値を求める（動的計画法）

問題

くだもの屋さんで、ミカンが $ x $ 個 $ a $ 円、 $ y $ 個 $ b $ 円、 $ z $ 個 $ c $ 円で売られています。

ミカンの買い方を工夫したとき、$ n $ 個のミカンを買うために必要な金額の最小値はいくらでしょうか。

（買い方を工夫した結果、買ったミカンが $ n + 1 $ 個以上になってもよいものとします。）

[条件]
🔹 $ x < y < z $
🔹 $ 1 \leqq n,x,y,z,a,b,c \leqq 1000 $

解法・ソースコード

memo[n] をちょうど $ n $ 個のミカンを買うのに必要な金額の最小値とすると、memo[0] ～ memo[k-1] と memo[k] の関係は memo[k] = min(memo[k - x] + a, memo[k - y] + b、memo[k - z] + c) となります。

memo を添字が大きい方から memo[k] = min(memo[k], memo[k + 1]) のように書き換えていけば、memo[n] が $ n $ 個以上のミカンを買うのに必要な金額の最小値となります。

$ n $ 個のミカンを最も安く手に入れたいときに $ n+z $ 個以上のりんごを買うのは無意味なので、memo は memo[n + z - 1] 程度まで計算しておけば大丈夫です。

[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 = 9              # 買いたいミカン数
x, a = 2, 100      # ミカンの個数と金額
y, b = 3, 125      # ミカンの個数と金額
z, c = 5, 200      # ミカンの個数と金額
#--------- 入力例2 ----------
# n = 145            # 買いたいミカン数
# x, a = 12,  752    # ミカンの個数と金額
# y, b = 102, 2483   # ミカンの個数と金額
# z, c = 703, 2810   # ミカンの個数と金額
#---------------------------
# 大きな数値（デフォルト値）
INF = 999999

# メモ化テーブル
memo = {}
memo[0] = 0

for i in range(1, n + z):
    memo[i] = min(memo.get(i, INF), memo.get(i - x, INF) + a)
    memo[i] = min(memo.get(i, INF), memo.get(i - y, INF) + b)
    memo[i] = min(memo.get(i, INF), memo.get(i - z, INF) + c)

print('解：', min(v for k, v in memo.items() if k >= n))

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

解： 375

3個125円のミカンを、3回分買うとトータル9個のミカンを 最小金額 375円 で買うことができます。

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

解： 2810

703個2810円のミカンを、1回分買うとトータル145個のミカンを 最小金額 2810円 で買うことができます。