全探索

全探索

次のような問題を考えます。

[問題]

500円玉がＡ枚、100円玉がＢ枚、50円玉がＣ枚あります。

これらの硬貨の中から何枚かを選び、合計金額をちょうどＸ円にする方法は

何通りありますか。

[条件]

・それぞれの枚数Ａ、Ｂ、Ｃは0以上かつ50以下の整数。
・目標金額Ｘは50以上かつ20000以下の50の倍数。
・それぞれの枚数の合計（Ａ＋Ｂ＋Ｃ）は1以上。

解法・ソースコード

この問題は、各硬貨の枚数分それぞれループを回して目標の金額になるかどうかをチェックすることで解くことができます。（三重ループしながら金額をチェック）

硬貨は 0枚 の時があるので、ループ回数は各硬貨の 枚数分 + 1 となることに注意してください。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#---------- 入力例 ----------
a = 2   # 500円玉の枚数
b = 2   # 100円玉の枚数
c = 2   # 50円玉の枚数
x = 100 # 目標金額
#----------------------------
res = 0     # 何通りあるかという解
# 全探索
for a1 in range(0, a + 1):          # 500円玉の枚数分ループ
    for b1 in range(0, b + 1):      # 100円玉の枚数分ループ
        for c1 in range(0, c + 1):  # 50円玉の枚数分ループ
            # 合計金額がＸ円に一致した場合
            if 500 * a1 + 100 * b1 + 50 * c1 == x:
                # それぞれの硬貨の枚数を出力
                print(f'500円{a1}枚、100円{b1}枚、50円{c1}枚')
                res += 1            # 解をカウントアップ
print('解：', res)

[実行結果]

500円0枚、100円0枚、50円2枚
500円0枚、100円1枚、50円0枚
解： 2

解は ２通り あることが分かりました。

硬貨の組み合わせは、合計金額が一致した場合のそれぞれの硬貨数を表示することで確認できます。