概要

本問題は、与えられた重さの荷物を積載量 \(M\) のトラックにすべて積み込むために必要な、最小のトラック台数を求める問題です。 荷物の個数 \(N\) が最大でも \(20\) と非常に小さいことを利用し、ビットDP（Bit DP）を用いることで効率的に解くことができます。

考察

貪欲法（Greedy）の限界

「重い荷物から順にトラックに詰める」といった貪欲な方法では、必ずしも最適な（最小の）台数になるとは限りません。 例えば、最大積載量 \(M = 10\)、荷物の重さが \([5, 4, 4, 3, 2, 2]\) の場合を考えます。 - 貪欲法: 重い順に詰めると、\([5, 4]\)（残り1）、\([4, 3, 2]\)（残り1）、\([2]\)（残り8）となり、3台必要になります。 - 最適解: \([5, 3, 2]\)（残り0）、\([4, 4, 2]\)（残り0）と分ければ、2台で運ぶことができます。

このように、荷物の組み合わせを全探索する必要がありますが、荷物の分け方の総数は非常に多くなります。

制約に着目する

荷物の個数 \(N\) に注目すると、\(1 \leq N \leq 20\) と非常に小さいです。 \(N\) 個の要素の「選ぶ・選ばない」の状態数は \(2^N\) 通りであり、\(N = 20\) のとき \(2^{20} \approx 10^6\) です。この程度の状態数であれば、すでに選んだ荷物の集合をビット列で表すビットDPが有効です。

DPの状態設計

「どの荷物を積み終えたか」という状態 \(S\)（\(0\) から \(2^N-1\) までの整数）に対して、必要なトラックの台数を最小化したいです。 しかし、単に「必要なトラックの台数」だけを記録していると、最後のトラックにあとどれだけの重さを積めるかが分からず、次の荷物を載せられるかどうかの判定ができません。

そこで、DPの値を以下の2つの情報のペアとして保持します。 - dp[S] = { 必要なトラックの最小台数, 最後のトラックの現在の積載量 }

このように定義すると、状態の優劣（どちらがより最適か）を std::pair の辞書順比較でそのまま評価できます。 1. 必要なトラックの台数が少ない方が良い。 2. トラックの台数が同じなら、最後のトラックの現在の積載量が少ない（＝残りの空き容量が多い）方が、次の荷物を載せやすいため良い。

アルゴリズム

1. 初期化:

   • dp 配列のすべての要素を十分大きな値（INF）で初期化します。
   • 何も載せていない初期状態 dp[0] を {1, 0} とします（1台目のトラックが空の状態で待機していることを表します）。

2. 遷移: 現在の状態を \(S\)、その時のDPの値を cnt（台数）と load（最後のトラックの積載量）とします。 まだ集合 \(S\) に含まれていない荷物 \(i\)（\(0 \leq i < N\)）を新しく載せることを考えます。

   • 同じトラックに載せられる場合 (\(load + W_i \leq M\)): トラックの台数は増えず、積載量が \(W_i\) だけ増えます。 遷移先：{cnt, load + W_i}
   • 新しいトラックが必要な場合 (\(load + W_i > M\)): 新しいトラックを1台追加し、そこに荷物 \(i\) を載せます。 遷移先：{cnt + 1, W_i}

この遷移先候補の値と、すでに記録されている dp[S | (1 << i)] の値を比較し、より小さい（最適な）方で更新します。

1. 答えの出力: すべての荷物を積み終えた状態である dp[(1 << N) - 1].first が、求める最小のトラック台数となります。

計算量

• 時間計算量: \(O(N 2^N)\) 状態数が \(2^N\) あり、各状態からまだ選んでいない荷物 \(N\) 個への遷移を試みるため、全体のループ回数は \(N 2^N\) 回となります。 \(N = 20\) のとき、 \(20 \times 2^{20} \approx 2 \times 10^7\) 回の演算となり、実行時間制限に余裕で間に合います。

• 空間計算量: \(O(2^N)\) サイズ \(2^N\) の std::pair の配列を保持するため、メモリ使用量は \(2^{20} \times 16 \text{ bytes} \approx 16 \text{ MB}\) となり、空間計算量も十分に小さく抑えられます。

実装のポイント

• std::pair の比較: C++の std::pair は、デフォルトで第1要素が優先して比較され、等しい場合に第2要素が比較されます（辞書順比較）。今回の「台数を最小化し、同値なら最後のトラックの積載量を最小化する」という目的に完全に一致するため、std::min をそのまま使って状態を更新することができます。

  ソースコード

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int INF = 1e9;

int main() {
    // 高速入出力
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    long long M;
    if (!(cin >> N >> M)) return 0;

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

    // dp[S] = {必要なトラックの最小台数, 最後のトラックの現在の積載量}
    vector<pair<int, long long>> dp(1 << N, {INF, INF});
    dp[0] = {1, 0};

    for (int S = 0; S < (1 << N); ++S) {
        if (dp[S].first == INF) continue;
        for (int i = 0; i < N; ++i) {
            if (!(S & (1 << i))) {
                int next_S = S | (1 << i);
                int cnt = dp[S].first;
                long long load = dp[S].second;
                
                pair<int, long long> next_val;
                if (load + W[i] <= M) {
                    next_val = {cnt, load + W[i]};
                } else {
                    next_val = {cnt + 1, W[i]};
                }
                
                dp[next_S] = min(dp[next_S], next_val);
            }
        }
    }

    cout << dp[(1 << N) - 1].first << "\n";

    return 0;
}

---

この解説は gemini-3.5-flash-high によって生成されました。