完全背包問題の基本概念

動的計画法（DP）における完全背包問題（Complete Knapsack Problem）は、各アイテムを無限に選択可能な状態での最適化問題を指します。0-1 背包問題との主な違いは、アイテムの再利用が許可されている点であり、これにより状態遷移の内側ループ順序が重要になります。具体的には、背包の容量を小さい方から大きい方へ順に更新することで、同一アイテムの複数回選択を表現できます。

主要な 4 つの実装パターン

完全背包問題は、求める答えの種類によって状態定義と遷移式が変化します。代表的な 4 つのパターンを以下に示します。

1. 最適値探索（最小化・最大化）

目標値を達成するための最小コストや最大価値を求めます。初期値には到達不可能を示す大きな値（または小さな値）を設定し、更新時に比較を行います。

int solveMinCost(vector<int>& denoms, int target_val) {
    const int UNREACHABLE = target_val + 1;
    vector<int> state(target_val + 1, UNREACHABLE);
    state[0] = 0;

    for (int i = 0; i < denoms.size(); ++i) {
        int val = denoms[i];
        for (int w = val; w <= target_val; ++w) {
            if (state[w - val] != UNREACHABLE) {
                state[w] = min(state[w], state[w - val] + 1);
            }
        }
    }
    return state[target_val] == UNREACHABLE ? -1 : state[target_val];
}

2. 組み合わせ数カウント

目標値を達成する方法の総数を計算します。初期状態として「0 を作る方法は 1 通り」と定義し、累積的に加算していきます。

int countCombinations(int target_val, vector<int>& denoms) {
    vector<unsigned int> ways(target_val + 1, 0);
    ways[0] = 1;

    for (int val : denoms) {
        for (int w = val; w <= target_val; ++w) {
            ways[w] += ways[w - val];
        }
    }
    return ways[target_val];
}

3. 到達可能性判定

特定の値を構成できるかどうかの真偽値を管理します。論理和（OR）を用いて状態を更新します。

bool isReachable(int target_val, vector<int>& denoms) {
    vector<bool> reachable(target_val + 1, false);
    reachable[0] = true;

    for (int val : denoms) {
        for (int w = val; w <= target_val; ++w) {
            if (reachable[w - val]) {
                reachable[w] = true;
            }
        }
    }
    return reachable[target_val];
}

4. 解の経路復元

最適値だけでなく、実際にどのアイテムを選択したかを特定します。遷移元の情報を別途記録し、最後に逆算します。

vector<int> reconstructPath(vector<int>& denoms, int target_val) {
    const int UNREACHABLE = target_val + 1;
    vector<int> state(target_val + 1, UNREACHABLE);
    vector<int> last_coin(target_val + 1, -1);
    state[0] = 0;

    for (int val : denoms) {
        for (int w = val; w <= target_val; ++w) {
            if (state[w - val] != UNREACHABLE) {
                if (state[w] > state[w - val] + 1) {
                    state[w] = state[w - val] + 1;
                    last_coin[w] = val;
                }
            }
        }
    }

    if (state[target_val] == UNREACHABLE) return {};

    vector<int> result;
    int curr = target_val;
    while (curr > 0 && last_coin[curr] != -1) {
        result.push_back(last_coin[curr]);
        curr -= last_coin[curr];
    }
    return result;
}

パターン別適用事例

上記のモデルを具体的なアルゴリズム問題に適用した事例を紹介します。

事例 1：最少硬貨数の計算

与えられた硬貨の面額を用いて、特定の金額を構成するのに必要な最小枚数を求めます。これは最適値探索パターンの典型例です。

入力条件: 硬貨配列 coins, 目標金額 amount
出力: 最小枚数（不可能な場合は -1）

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int max_val = amount + 1;
        vector<int> dp(amount + 1, max_val);
        dp[0] = 0;

        for (int c : coins) {
            for (int i = c; i <= amount; ++i) {
                dp[i] = min(dp[i], dp[i - c] + 1);
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
};

事例 2：金額構成の組み合わせ総数

硬貨の順序を考慮せず、金額を構成する組み合わせのパターン数を算出します。順序を考慮しないため、外側ループを硬貨種類、内側ループを金額に設定します。

入力条件: 目標金額 amount, 硬貨配列 coins
出力: 組み合わせ数

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<int> dp(amount + 1, 0);
        dp[0] = 1;

        for (int coin : coins) {
            for (int j = coin; j <= amount; ++j) {
                dp[j] += dp[j - coin];
            }
        }
        return dp[amount];
    }
};

事例 3：完全平方数の最小個数

整数 n を完全平方数（1, 4, 9, 16...）の和で表すとき、必要な項の最小数を求めます。硬貨の面額が「平方数」である特殊な完全背包問題と捉えられます。

入力条件: 整数 n
出力: 完全平方数の最小個数

class Solution {
public:
    int numSquares(int n) {
        vector<int> dp(n + 1, 1e9);
        dp[0] = 0;

        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j * j <= i; ++j) {
                int square = j * j;
                dp[i] = min(dp[i], dp[i - square] + 1);
            }
        }
        return dp[n];
    }
};

事例 4：コスト制約下的最大数値構築

各数字（1〜9）に対応するコストがあり、総コストの制限内で作れる最大の数値（桁数が多く、辞書順で大きい）を求めます。まず DP で最大桁数を求め、その後貪欲法で数字を決定します。

入力条件: コスト配列 cost, 目標コスト target
出力: 構築可能な最大の数値（文字列）

class Solution {
public:
    string largestNumber(vector<int>& cost, int target) {
        vector<int> dp(target + 1, -1e9);
        dp[0] = 0;

        // 最大桁数を DP で計算
        for (int t = 1; t <= target; ++t) {
            for (int d = 1; d <= 9; ++d) {
                int c = cost[d - 1];
                if (t >= c && dp[t - c] >= 0) {
                    dp[t] = max(dp[t], dp[t - c] + 1);
                }
            }
        }

        if (dp[target] < 0) return "0";

        // 貪欲的に数字を復元（大きい数字から優先）
        string ans = "";
        int curr = target;
        for (int d = 9; d >= 1; --d) {
            int c = cost[d - 1];
            while (curr >= c && dp[curr] == dp[curr - c] + 1) {
                ans += to_string(d);
                curr -= c;
            }
        }
        return ans;
    }
};

状態遷移の比較まとめ