概要

\(N \leq 20\) と小さいため、荷物の集合をビットで表す bit DP を使います。
各集合について「現在のトラックの積載量」と「それまでに使い終わったトラック台数」を管理し、必要なトラック台数の最小値を求めます。

考察

この問題は、荷物をいくつかのグループに分け、それぞれの合計重さが \(M\) 以下になるようにして、グループ数を最小化する問題です。

つまり、各グループが 1 台のトラックに対応します。

素朴に考えると、各荷物をどのトラックに載せるかを全探索したくなりますが、トラックの分け方は非常に多く、単純な全探索では間に合いません。

また、「順番に見て、今のトラックに入るなら入れる」という貪欲法も正しくありません。

例えば、\(M=10\)、荷物が

\(4, 8, 2, 6\)

のとき、入力順に詰めると

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

となり 3 台必要に見えます。

しかし実際には、

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

とすれば 2 台で済みます。

したがって、荷物を載せる順番も含めてうまく探索する必要があります。

ここで \(N \leq 20\) なので、荷物の部分集合は最大で

\(2^{20}\)

通りです。
これは約 100 万通りなので、部分集合 DP が使えます。

アルゴリズム

荷物の集合を bitmask で表します。

• \(mask\) の \(i\) ビット目が \(1\) なら、荷物 \(i\) はすでに積み込み済み
• \(0\) なら、まだ積み込んでいない

とします。

DP では、各 \(mask\) について次の情報を持ちます。

• すでに使い終わったトラック台数
• 現在積み込み中のトラックの積載量

例えば、状態を \((c, x)\) とします。

• \(c\): 現在のトラックより前に、すでに使い終わったトラック台数
• \(x\): 現在のトラックに載っている重さ

このとき、最終的なトラック台数は \(c+1\) です。

ただし、同じ \(mask\) に対して複数の状態が考えられます。
その中で良い状態は、

1. 使い終わったトラック台数 \(c\) が少ない
2. \(c\) が同じなら、現在の積載量 \(x\) が小さい

ものです。

現在の積載量が小さいほど、残り容量が大きく、今後の荷物を載せやすいためです。

したがって、各 \(mask\) について最良の \((c, x)\) だけを持てば十分です。

遷移

現在の状態が \(mask\) で、まだ載せていない荷物 \(i\) を次に載せるとします。

現在のトラックの積載量を \(x\)、荷物 \(i\) の重さを \(W_i\) とすると、

今のトラックに載る場合

\(x + W_i \leq M\)

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

状態は

\((c, x + W_i)\)

になります。

今のトラックに載らない場合

\(x + W_i > M\)

なら、新しいトラックを使います。

現在のトラックは使い終わるので、使い終わったトラック台数が 1 増えます。

状態は

\((c+1, W_i)\)

になります。

この遷移を、すべての \(mask\) と、まだ載せていない荷物について行います。

コードでの状態の持ち方

コードでは、\((c, x)\) を 1 つの整数にエンコードしています。

base = M + 1
value = c * base + x

ここで \(0 \leq x \leq M\) なので、\(base=M+1\) とすると、整数の大小比較がそのまま

1. \(c\) が小さい
2. \(c\) が同じなら \(x\) が小さい

という比較になります。

つまり、

if cand < dp[nmask]:
    dp[nmask] = cand

だけで、より良い状態を選べます。

最後に、全荷物を積み込んだ状態を full とすると、

dp[full] // base

が使い終わったトラック台数 \(c\) です。
現在のトラックも 1 台として数えるので、答えは

dp[full] // base + 1

になります。

計算量

部分集合は \(2^N\) 個あります。
各部分集合について、まだ載せていない荷物を最大 \(N\) 個試します。

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

\(N \leq 20\) なので、十分間に合います。

実装のポイント

dp[mask] には、エンコードした値を保存しています。

base = M + 1
dp[0] = 0

これは、最初に空のトラックが 1 台あるとみなして、

• 使い終わったトラック台数 \(0\)
• 現在の積載量 \(0\)

という状態を表しています。

また、荷物 \(i\) の bit だけが立った値は 1 << i です。
コードでは、その bit に対応する荷物の重さをすぐ取得できるようにしています。

bit_w = [0] * size
for i, w in enumerate(W):
    bit_w[1 << i] = w

未使用の荷物は、

rem = full ^ mask

で求められます。

その後、

b = rem & -rem

によって、未使用の荷物のうち 1 つの bit を取り出しています。

これにより、bit を効率よく列挙できます。

ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    N, M = data[0], data[1]
    W = data[2:]

    if N == 0:
        print(0)
        return
    if sum(W) <= M:
        print(1)
        return

    size = 1 << N
    full = size - 1
    base = M + 1
    INF = (N + 1) * base

    dp = [INF] * size
    dp[0] = 0

    bit_w = [0] * size
    for i, w in enumerate(W):
        bit_w[1 << i] = w

    for mask in range(size):
        val = dp[mask]
        load = val % base
        space = M - load
        opened = val - load + base
        rem = full ^ mask

        while rem:
            b = rem & -rem
            w = bit_w[b]
            nmask = mask + b

            if w <= space:
                cand = val + w
            else:
                cand = opened + w

            if cand < dp[nmask]:
                dp[nmask] = cand

            rem ^= b

    print(dp[full] // base + 1)

if __name__ == "__main__":
    main()

---

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