概要

\(N\) 個の荷物（\(N \leq 20\)）を、最大積載量 \(M\) のトラックに積み込むとき、必要なトラックの最小台数を求める問題です。これは典型的な「ビンパッキング問題」であり、\(N\) が小さいことから bit DP（部分集合に対する動的計画法） で解けます。

考察

素朴なアプローチの問題点

「すべての荷物のトラックへの割り当て方を全探索する」と考えると、組み合わせの数が膨大になり間に合いません。各荷物がどのトラックに乗るかを全列挙すると、台数も不定で扱いにくくなります。

重要な観察

ここで注目すべきは \(N \leq 20\) という制約です。これは「どの荷物をすでに積んだか」を bit（\(2^N\) 通り） で表現できることを示唆しています。

そこで、「荷物の集合」を状態とする DP を考えます。荷物の部分集合 \(S\) について、

• その集合を積むのに必要な最小トラック台数
• （台数が同じなら）最後に使っているトラックの残り積載量を最大化

という情報を持つことにします。

なぜ「残り積載量の最大化」が重要かというと、最後のトラックに空きが多いほど、次に追加する荷物を新しいトラックを使わずに積める可能性が高くなり、将来的に得をするからです。台数が同じなら残り容量は多いほど良い、という関係（優越関係）が成り立つため、各集合についてこの 1 つの最良状態だけを保持すれば十分です。

この DP では「トラックを 1 台ずつ順番に満たしていき、開いているトラックは常に最後の 1 台だけ」という形で荷物を詰めます。どんな積み方も、トラックを順番に埋めていく形に並べ替えられるので、この方針で最適解が得られます。

アルゴリズム

各部分集合 mask に対し、状態 (トラック台数 trucks, 最後のトラックの残り容量 space) を管理します。この 2 つの値を 1 つの整数に符号化して扱うと比較が簡単になります。

符号化の工夫

\(K = M + 1\) とし、状態を次の値で表します。

\[\text{value} = \text{trucks} \times K + (M - \text{space})\]

• 第 1 項 \(\text{trucks} \times K\) が台数を表し、\(K = M+1\) なので台数が 1 増えると必ず第 2 項より大きく増加します。
• 第 2 項 \(M - \text{space}\) は「最後のトラックの使用済み容量」を表します。

この値を 最小化 することで、「まず台数を最小化し、台数が同じなら使用済み容量を最小化（＝残り容量を最大化）」という優先順位が自然に実現されます。

遷移

初期状態は dp[0] = M（= \(0 \times K + M\)）とします。これは「台数 0、残り容量 0」を意味し、最初の荷物を積む際に必ず新しいトラックを開くようになっています。

集合 mask（値 cur）から、まだ積んでいない荷物 \(i\)（重さ \(w_i\)）を追加するとき：

• 現在のトラックに乗る場合（\(w_i \leq \text{space}\)）： nval = cur + wi（台数そのまま、使用量が \(w_i\) 増える）
• 新しいトラックが必要な場合（\(w_i > \text{space}\)）： nval = (trucks + 1) * K + wi（台数 +1、新トラックに \(w_i\) 積む）

得られた nval が dp[mask | (1 << i)] より小さければ更新します。

最後に dp[full] // K（full は全荷物を積んだ状態）で最小台数が求まります。

計算量

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

\(N \leq 20\) より \(2^{20} \times 20 \approx 2 \times 10^7\) 程度で、十分高速に動作します。

実装のポイント

• 2 つの値を 1 整数に符号化するのがこのコードの肝です。\(K = M+1\) という底を使うことで、trucks = cur // K、使用済み容量 = cur % K と簡単に復元でき、また大小比較だけで「台数優先・残容量最大」の最適化が同時に実現できます。

• 初期状態を「残り容量 0」とすることで、最初の荷物が自動的に新トラックを開くように設計しており、場合分けがシンプルになっています。

• 各荷物は \(W_i \leq M\) が保証されているため、単体では必ずどこかのトラックに積めます（無限ループや積めない事態は起きません）。

  ソースコード

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0]); M = int(data[1])
    w = [int(data[2 + i]) for i in range(n)]
    full = (1 << n) - 1
    K = M + 1
    INF = float('inf')
    size = 1 << n
    dp = [INF] * size
    # encode value = trucks * K + (M - space)  (minimize)
    dp[0] = M  # 0 trucks, space 0
    for mask in range(size):
        cur = dp[mask]
        if cur == INF:
            continue
        trucks = cur // K
        space = M - (cur % K)
        next_truck_base = (trucks + 1) * K
        for i in range(n):
            if not (mask >> i) & 1:
                wi = w[i]
                if wi <= space:
                    nval = cur + wi
                else:
                    nval = next_truck_base + wi
                nm = mask | (1 << i)
                if nval < dp[nm]:
                    dp[nm] = nval
    print(dp[full] // K)

main()

---

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