切手の最小枚数の組み合わせを動的計画法で解く

郵便料金を支払うために必要な最小枚数の切手の組み合わせを求める問題を動的計画法（DP）を使って効率的に解く方法について解説します。この問題は、いわゆる「コイン問題」と似た性質を持ち、動的計画法の典型的な応用例の一つです。

問題の定義

与えられた一連の切手の額面（例えば、10円、60円、100円など）を使って、指定された料金（例えば、120円）を支払うために必要な最小枚数の切手を求める問題です。切手の額面は無限に枚数があるものとします。

例

切手の額面: 10円, 60円, 100円
支払う料金: 120円

この場合、最小枚数で120円を支払うためには、60円の切手を2枚使うのが最小となります。なお、金額の大きいほうから引く計算をすると（120-100=20で、残り20円を10円切手2枚とすると、計3枚となる）、正しい解が得られないので注意です。

解法のアプローチ

この問題は、「最小枚数で特定の金額を作る」という部分がコイン問題に似ているため、動的計画法（DP）を使うことで効率的に解けます。動的計画法を使用すると、部分問題を解決することで最終的な解を得ることができます。

動的計画法のステップ

1. 状態定義
   dp[i]を、金額iを作るために必要な最小枚数の切手と定義します。

2. 初期条件
   dp[0] = 0とします。0円を作るためには切手が0枚で十分です。

3. 遷移式
   各金額iについて、切手の額面c（10円、50円、100円など）を使って金額iを作る場合、次の遷移式を使います。
   $$
   dp[i] = \min(dp[i], dp[i - c] + 1)
   $$
   これは、金額i - cを作るための最小枚数に1枚の切手cを足したものを比較するという意味です。

4. 最終的な解
   dp[target]（指定された料金target）が、最小枚数の切手の枚数を示します。

実装

以下にPythonで実装したコードを示します。

def min_stamps(target, stamps):
    # dp[i] : 金額iを作るための最小枚数
    dp = [float('inf')] * (target + 1)
    dp[0] = 0  # 0円を作るためには0枚の切手でOK

    for i in range(1, target + 1):
        for stamp in stamps:
            if i - stamp >= 0:
                dp[i] = min(dp[i], dp[i - stamp] + 1)

    return dp[target] if dp[target] != float('inf') else -1  # 目標金額を作れない場合は-1を返す

# 使用例
stamps = [10, 60, 100]  # 切手の額面
target = 120  # 支払う金額
result = min_stamps(target, stamps)
print(f"最小枚数の切手: {result}")

実行結果

最小枚数の切手: 2

しっかり正しい答えが出ました。