概要

\(N\) 個の荷物を、容量 \(M\) のトラックに分けて積むとき、必要なトラック台数の最小値を求める問題です。

\(N \leq 20\) と小さいため、荷物の集合をビットで表す bit DP を使って解きます。

考察

この問題は「容量制限のある箱に、全ての荷物を分ける」問題です。

単純に各荷物をどのトラックに載せるか全探索すると、組み合わせ数が非常に大きくなり、\(N=20\) でも間に合いません。

また、例えば「順番に積めるだけ積む」という貪欲法も正しくありません。

例として、\(M=10\)、荷物が \(6,6,4,4\) の場合を考えます。

順番に積むと、

• 1台目: \(6\)
• 2台目: \(6+4=10\)
• 3台目: \(4\)

となり、3台必要になります。

しかし最適には、

• 1台目: \(6+4=10\)
• 2台目: \(6+4=10\)

で、2台で済みます。

そのため、全ての組み合わせをうまく調べる必要があります。

ここで \(N \leq 20\) なので、荷物の集合をビットマスクで表すことができます。

各集合について、

• その集合の荷物を運ぶために必要な最小トラック台数
• そのとき最後のトラックに載っている重さ

を管理します。

重要なのは、トラック台数が同じなら「最後のトラックの使用済み重量が小さい方が良い」ということです。

例えば、同じく2台使っていても、最後のトラックの重さが \(9\) より \(5\) の方が、あとから別の荷物を追加しやすくなります。

アルゴリズム

ビットマスク \(mask\) を「すでに積み込んだ荷物の集合」とします。

\(dp[mask]\) を次のように定義します。

\(dp[mask] = (a, b)\)

• \(a\): \(mask\) に含まれる荷物を運ぶために必要な最小トラック台数
• \(b\): そのとき、最後のトラックに載っている荷物の合計重量の最小値

初期状態は、

\(dp[0] = (1, 0)\)

です。

これは「空のトラックを1台用意していて、まだ何も載せていない」と考えます。

次に、各 \(mask\) について、最後に追加する荷物 \(i\) を全て試します。

荷物 \(i\) が \(mask\) に含まれているとき、

\(prev = mask \setminus \{i\}\)

とします。

つまり、\(prev\) は荷物 \(i\) を取り除いた集合です。

まず \(dp[prev]\) の状態から始めます。

最後のトラックに荷物 \(i\) を追加できるなら、

\(b + W_i \leq M\)

なので、同じトラックに載せます。

この場合、状態は

\((a, b + W_i)\)

になります。

一方、最後のトラックに載せられないなら、新しいトラックを使います。

この場合、状態は

\((a+1, W_i)\)

になります。

これを全ての \(i\) について試し、次の優先順位で最良のものを選びます。

1. トラック台数が少ない
2. トラック台数が同じなら、最後のトラックの重量が小さい

最終的な答えは、

\(dp[(1 << N) - 1]\)

のトラック台数です。

計算量

• 時間計算量: \(O(N2^N)\)
• 空間計算量: \(O(2^N)\)

\(N \leq 20\) なので、\(2^N\) は最大でも約 \(10^6\) であり、十分間に合います。

実装のポイント

• \(mask\) の \(i\) ビット目が立っているかどうかで、荷物 \(i\) が集合に含まれるかを判定します。

• mask ^ (1 << i) により、\(mask\) から荷物 \(i\) を取り除いた集合を作れます。

• 重さ \(W_i\) や容量 \(M\) は最大 \(10^9\) なので、long long を使います。

• dp[0] = {1, 0} とすることで、最初の荷物も通常の遷移で処理できます。

  ソースコード

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    long long M;
    cin >> N >> M;

    vector<long long> W(N);
    for (int i = 0; i < N; i++) cin >> W[i];

    int total = 1 << N;
    const int INF = 1e9;

    vector<pair<int, long long>> dp(total, {INF, 0});
    dp[0] = {1, 0};

    for (int mask = 1; mask < total; mask++) {
        pair<int, long long> best = {INF, 0};

        for (int i = 0; i < N; i++) {
            if (!(mask & (1 << i))) continue;

            auto cur = dp[mask ^ (1 << i)];

            if (cur.second + W[i] <= M) {
                cur.second += W[i];
            } else {
                cur.first++;
                cur.second = W[i];
            }

            if (cur.first < best.first ||
                (cur.first == best.first && cur.second < best.second)) {
                best = cur;
            }
        }

        dp[mask] = best;
    }

    cout << dp[total - 1].first << '\n';

    return 0;
}

---

この解説は gpt-5.5-high によって生成されました。