概要

\(N \le 15\) 個の荷物を、合計重量が \(C\) 以下になるように何回かに分けて運ぶとき、必要な最小往復回数（グループ数）を求めます。

考察

この問題は本質的に「荷物をいくつかのグループに分け、各グループの合計が \(C\) 以下」という 分割（bin packing） です。一般には難しい問題ですが、今回は \(N \le 15\) と小さいため、全ての部分集合を状態として持つDP が可能です。

素朴に「全ての分け方（グループ分け）を列挙」すると、分割の仕方は爆発的に増え（ベル数のオーダー）、\(N=15\) でも現実的ではありません。また、貪欲法（重い順に詰めるなど）は最適解を保証できず、WAになります。

そこで、「今どの荷物を運び終えたか」を bitmask（部分集合）で管理しつつ、
(往復回数, 現在の便に積んでいる重さ) を最適化するDPを行うと、\(2^N\) 状態で解けます。

ポイントは、最小化したいのは往復回数ですが、同じ往復回数なら「現在便の積載量が小さい」ほうが将来詰めやすく有利、ということです。よって状態の評価を - 往復回数を最小 - 同じなら現在の積載量を最小
という 辞書順（lexicographical） で比較します。

アルゴリズム

状態

\(mask\) を「運び終えた荷物の集合」（\(N\) ビット）とします。

DP配列： - \(dp[mask] = (r, s)\)
- \(r\): これまでに使った往復回数（便の数） - \(s\): 最後の便（現在使っている便）に積んでいる合計重量

ここで \((r, s)\) は辞書順で最小のものを保持します。

初期状態： - \(dp[0] = (1, 0)\)
まだ何も運んでいないが、「これから1便目に積み始める」と考えると遷移が簡単になります。

遷移

各 \(mask\) について、まだ運んでいない荷物 \(i\) を1つ追加することを考えます。

• もし \(s + W_i \le C\) なら、同じ便に載せられる：
  • \(dp[mask \cup \{i\}]\) の候補は \((r, s + W_i)\)
• そうでなければ、新しい便を開始する：
  • 候補は \((r + 1, W_i)\)

これを全ての \(mask\) と全ての \(i\) について行い、最小のものを更新します。

例（イメージ）

\(C=10\), 荷物が \([6,5,4]\) のとき、 - まず \(6\) を積むと現在便は \(6\) - 次に \(5\) は \(6+5=11\) で無理なので、便を増やして新便に \(5\) - そこへ \(4\) を積むと \(5+4=9\) でOK
結果、2便で運べます。

この「最後の便の積載量 \(s\) を持っておく」ことで、「あと何が同じ便に入るか」を正しく管理できます。

計算量

• 時間計算量: \(O(N \cdot 2^N)\)
  各 \(mask\)（\(2^N\) 個）から、最大 \(N\) 個の荷物追加を試すため。
• 空間計算量: \(O(2^N)\)
  \(dp\) に \(2^N\) 状態を保持するため。

実装のポイント

• Pythonではタプル同士が辞書順比較できるので、cand < dp[nmask] のように書くだけで
  「往復回数が小さい方、同じなら積載量が小さい方」を自然に選べます。

• 初期値を dp[0] = (1, 0) とするのがコツです（便数を0から始めると場合分けが増えます）。

• 最終的な答えは dp[(1<<N)-1][0]（全て運び終えた状態の往復回数）です。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N, C = map(int, input().split())
    W = list(map(int, input().split()))
    M = 1 << N

    INF = 10**18
    dp = [(INF, INF)] * M
    dp[0] = (1, 0)

    for mask in range(M):
        rides, load = dp[mask]
        for i in range(N):
            if mask & (1 << i):
                continue
            nmask = mask | (1 << i)
            if load + W[i] <= C:
                cand = (rides, load + W[i])
            else:
                cand = (rides + 1, W[i])
            if cand < dp[nmask]:
                dp[nmask] = cand

    print(dp[M - 1][0])

if __name__ == "__main__":
    main()

---

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