概要

\(N\) 個の荷物（重さ \(W_i\)）を、最大積載量 \(M\) のトラックに分割して載せるとき、必要なトラックの最小台数を求める問題です。これはいわゆる「ビンパッキング問題」の最小化版です。

考察

まず素朴に考えると、「各荷物をどのトラックに載せるか」を全パターン試す方法があります。しかしトラックの台数も自由なので、割り当ての組み合わせは非常に多く、単純な全探索では破綻します。

ここで重要なのは制約 \(N \leq 20\) です。\(N\) が小さいので、「どの荷物の集合を既に積み込んだか」を \(N\) ビットのビットマスクで管理することができます。\(2^{20} \approx 10^6\) なので、集合をすべて状態として持っても十分間に合います。

さて、荷物の集合に対して「最小トラック数」を求めたいのですが、ただトラック数だけを覚えていると困ることがあります。それは「今使っているトラックにあとどれだけ積めるか」という情報が必要になるからです。

そこで、状態として次の 2 つを組にして持ちます。

• 使用したトラックの台数（最後の 1 台を含む）
• 最後（現在）のトラックに既に積んだ重さの合計

この 2 つがあれば、新しい荷物を加えるときに「今のトラックに載るか」「新しいトラックを使う必要があるか」を判定できます。

そして、同じ荷物集合を達成する状態が複数ある場合は、

1. まずトラック台数が少ない方が良い
2. 台数が同じなら、最後のトラックに積んだ重さが少ない方が良い（残り容量が多く、今後の荷物を載せやすいため）

という優先順位（辞書順最小）で最良の状態を 1 つだけ保持すれば十分です。台数が同じで残り容量が大きい状態は、小さい状態が「できること」をすべてできるので、この比較は正当です。

アルゴリズム

ビットマスクを用いた DP を行います。

• dp[mask] = (トラック台数, 最後のトラックに積んだ重さ) のうち辞書順最小のもの
• 初期状態：dp[0] = (1, 0)（荷物 0 個でもトラックを 1 台用意した状態とみなす）

遷移は、まだ積んでいない荷物 \(i\) を 1 つ選び、現在の状態 \((g, r)\) から次のように行います。

• \(r + W_i \leq M\) のとき（今のトラックに載る）：新状態は \((g,\; r + W_i)\)
• そうでないとき（載らないので新しいトラックを使う）：新状態は \((g+1,\; W_i)\)

得られた候補が dp[mask | (1<<i)] より辞書順で小さければ更新します。

すべての荷物を積んだ状態 dp[full]（full = (1<<N) - 1）のトラック台数が答えです。

具体例として \(M = 10\)、荷物が \(\{6, 4, 5, 5\}\) の場合を考えると、\(\{6,4\}\) と \(\{5,5\}\) の 2 台に分けられるため、答えは \(2\) になります。DP は荷物を 1 つずつ加えながら、こうした詰め方を自動的に探索します。

計算量

• 時間計算量: \(O(2^N \cdot N)\)
  • 各マスク（\(2^N\) 通り）について、加える荷物の候補 \(N\) 個を試すため。\(N=20\) で約 \(2 \times 10^7\) 回の操作となり、十分高速です。
• 空間計算量: \(O(2^N)\)
  • dp 配列のサイズが \(2^N\) です。

実装のポイント

• 最大積載量 \(M\) や重さの合計は最大で \(10^9 \times 20 = 2 \times 10^{10}\) 程度になり得るため、重さや積載量は 64 ビット整数（long long） で扱います。

• 状態の比較は pair<int, long long> の標準の辞書順比較を使うと、「台数を優先し、同点なら積んだ重さを比較」がそのまま実現でき、実装が簡潔になります。

• 未到達の状態（台数が INT_MAX）はスキップすることで無駄な遷移を省けます。なお初期状態を dp[0] = (1, 0) としているため、荷物が 0 個でないかぎり最終的に正しい台数が求まります（制約上 \(N \geq 1\) なので問題ありません）。

  ソースコード

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

int main(){
    int N; long long M;
    cin >> N >> M;
    vector<long long> w(N);
    for(int i=0;i<N;i++) cin >> w[i];
    
    int full = (1<<N) - 1;
    // dp[mask] = (groups, used in last group), minimize groups then used
    vector<pair<int,long long>> dp(1<<N, {INT_MAX, 0});
    dp[0] = {1, 0};
    for(int mask=0; mask<(1<<N); mask++){
        if(dp[mask].first == INT_MAX) continue;
        auto [g, r] = dp[mask];
        for(int i=0;i<N;i++){
            if(mask & (1<<i)) continue;
            int nmask = mask | (1<<i);
            pair<int,long long> cand;
            if(r + w[i] <= M){
                cand = {g, r + w[i]};
            } else {
                cand = {g+1, w[i]};
            }
            if(cand < dp[nmask]) dp[nmask] = cand;
        }
    }
    cout << dp[full].first << "\n";
    return 0;
}

---

この解説は claude4.8opus-high によって生成されました。