概要

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

考察

制約を見ると \(N \le 20\) と非常に小さいです。このような場合、荷物の集合をビット列（0と1の列）で表現し、すべての状態を管理する「bitDP（ビット動的計画法）」が有効な場合が多いです。

荷物をどのトラックに載せるかの組み合わせは膨大にありますが、前から順に荷物をトラックに載せていくことを考えます。「すでにトラックに載せた荷物の集合 \(S\)」が決まっているとき、今後の荷物の載せ方を最適化するためには、現在の状態として以下の2つの情報だけがわかっていれば十分です。 1. 使っているトラックの台数 2. 現在積み込んでいる（最後に使っている）トラックの積載量

もし「使っているトラックの台数」が同じで、かつ「最後のトラックの積載量」が少ない状態があれば、それ以降の荷物の載せ方において明らかに有利です。したがって、各集合 \(S\) についてこの2つの値を最小化するようにDPを行えばよいことがわかります。

貪欲法（重い荷物から順に載せるなど）では、特定のケースで台数が多くなってしまい正答（WA）となる可能性があるため、DPで厳密に探索します。

アルゴリズム

bitDP（部分集合DP）を用います。

状態 dp[S] を、荷物の集合 \(S\) をトラックに載せ終わったときの最適な状態として、タプル (トラックの台数, 最後のトラックの積載量) で定義します。

初期状態は何も荷物を載せていない状態ですが、1台目のトラックを用意したとみなして dp[0] = (1, 0) とします。

各状態 \(S\) から、まだ載せていない荷物 \(i\) を追加することを考えます。荷物 \(i\) の重さを \(w\) とします。 - 現在の最後のトラックに余裕がある場合（used + w <= M）：同じトラックに載せられます。次の状態は (cost, used + w) になります。 - 余裕がない場合：新しいトラックを用意して載せます。次の状態は (cost + 1, w) になります。

この遷移をすべての \(S\) と \(i\) について行います。Pythonのタプル比較では、前の要素（台数）が小さい方が優先され、同じ場合は後ろの要素（積載量）が小さい方が優先されます。これを利用して dp テーブルを更新していきます。

最終的に、すべての荷物を載せた状態 dp[(1 << N) - 1] のトラック台数が答えとなります。

計算量

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

実装のポイント

• Pythonではタプルを用いて状態を管理すると、自動的に「台数が少なく、かつ積載量が少ない」状態を最小値として比較・更新できるため簡潔に実装できます。

• 配列の初期値には十分に大きな値（例えば (1 << 30, 0) など）を設定しておきます。

• 荷物を1つも載せていない初期状態 dp[0] を (1, 0) とすることで、「最初から1台目のトラックを準備している」状態を作り、荷物を追加する際の分岐（同じトラックに載せるか、次のトラックに載せるか）をシンプルにしています。

  ソースコード

import sys

def solve():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    W = list(map(int, input().split()))
    
    INF = (1 << 30, 0)
    dp = [INF] * (1 << N)
    dp[0] = (1, 0)
    
    for S in range(1 << N):
        cost, used = dp[S]
        if cost == (1 << 30):
            continue
        for i in range(N):
            if not (S & (1 << i)):
                w = W[i]
                if used + w <= M:
                    nxt = (cost, used + w)
                else:
                    nxt = (cost + 1, w)
                if nxt < dp[S | (1 << i)]:
                    dp[S | (1 << i)] = nxt
    
    print(dp[(1 << N) - 1][0])

solve()

---

この解説は or-glm5.2-high によって生成されました。