概要

\(N\) 個の荷物をエレベーターで運ぶとき、積載重量制限 \(C\) を超えないようにグループ分けし、必要な最小の往復回数を求める問題です。

考察

この問題は「荷物を何回の運搬で全部運べるか？」という最適化問題です。
素朴な方法として、貪欲法（例えば、重いものから順に詰めていく）などが考えられますが、荷物の数 \(N\) が最大 \(15\) であり、全探索が可能であるため、厳密な解法で解くのが確実です。

重要な観察は、荷物の選び方（つまりどの荷物を一緒に運ぶか）をビット集合（bitmask）で表現できることです。
例えば、荷物が \(4\) 個あるとき、集合 \(\{0, 2\}\) は \(0\) 番目と \(2\) 番目の荷物を選ぶことを意味します。

全探索の基本戦略は次の通りです： 1. すべての荷物の部分集合について、その合計重量が \(C\) 以下かどうかを前計算しておきます。 2. すでに使った荷物の集合を状態として持つ動的計画法（DP）を行い、最小の往復回数を求めます。

このように、部分集合の組み合わせを全探索する方法は「部分集合の列挙＋DP」で実現できます。

アルゴリズム

この問題では、ビットマスクを用いた動的計画法（bit DP）を用います。

ステップ

1. 前処理：すべての部分集合について、その荷物の重さの合計が \(C\) 以下であるかを判定し、有効な部分集合をリストアップします。
2. DPの定義：
   • dp[mask] := すでに運んだ荷物の集合が mask のときの最小往復回数
   • 初期値：dp[0] = 0（何も運んでいない状態）、それ以外は無限大
3. DPの更新：
   • 現在の状態 mask に対して、まだ使っていない荷物の集合 unused を求めます。
   • unused のすべての部分集合（空集合を除く）について、それが有効（合計重量 \(\leq C\)）であれば、 new_mask = mask | subset として遷移します：

     
     dp[new_mask] = min(dp[new_mask], dp[mask] + 1)
     

4. 答え：dp[(1 << N) - 1] が最終的な最小往復回数です。

具体例

例えば \(N=3\), \(C=10\), 荷物が [3, 5, 7] のとき： - 単品ではすべて運べるが、\(\{3, 5\}\) はOK、\(\{5, 7\}\) はNG。 - 最適な運び方は：1回目で \(\{3, 5\}\)、2回目で \(\{7\}\) → 合計2回。

計算量

• 時間計算量: \(O(3^N)\)
  • 各状態に対して、残りの荷物の部分集合を列挙するのに \(O(2^{N})\) かかる操作が、全体で \(O(3^N)\) になります（有名な部分集合の列挙の計算量）。
• 空間計算量: \(O(2^N)\)
  • DPテーブルのサイズが \(2^N\)

実装のポイント

• ビット演算で部分集合をうまく扱う必要がある。
• 「ある集合の部分集合を全列挙する」イディオムは頻出なので、以下のように書けることを覚えておくと便利：

  
  submask = unused
  while submask > 0:
    # 何か処理
    submask = (submask - 1) & unused
  

• 合計重量を毎回計算せず、前処理で有効な部分集合を列挙しておくことで高速化可能（今回のコードでは毎回計算しているので、必要があれば前処理版も検討）。

## ソースコード

```python
from itertools import combinations

def main():
    N, C = map(int, input().split())
    W = list(map(int, input().split()))
    
    # 全ての部分集合について、その和がC以下かどうかを前計算
    valid_subsets = []
    for mask in range(1 << N):
        total = 0
        subset = []
        for i in range(N):
            if mask & (1 << i):
                total += W[i]
                subset.append(i)
        if total <= C:
            valid_subsets.append((mask, total))
    
    # dp[mask] := 使用した荷物の集合がmaskであるときの最小往復回数
    INF = float('inf')
    dp = [INF] * (1 << N)
    dp[0] = 0
    
    # 各状態に対して、有効な部分集合を加えた新しい状態に遷移
    for mask in range(1 << N):
        if dp[mask] == INF:
            continue
        # まだ使っていない荷物の集合
        unused = ((1 << N) - 1) ^ mask
        # unusedの部分集合をすべて試す（空集合は除く）
        submask = unused
        while submask > 0:
            # submaskがvalidかチェック
            is_valid = False
            total_weight = 0
            for i in range(N):
                if submask & (1 << i):
                    total_weight += W[i]
            if total_weight <= C:
                is_valid = True
            
            if is_valid:
                new_mask = mask | submask
                dp[new_mask] = min(dp[new_mask], dp[mask] + 1)
            
            submask = (submask - 1) & unused
    
    print(dp[(1<<N)-1])

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。