概要

\(N\) 個の荷物を \(M\) 台のトラックに、各トラックの積載重量制限を守りながら全て積めるかを判定する問題です。バックトラッキング（深さ優先探索）と枝刈りを組み合わせて解きます。

考察

問題の性質

この問題は「ビンパッキング問題」の一種で、NP困難な問題として知られています。しかし、\(N, M \leq 15\) という小さな制約があるため、工夫した全探索で解けます。

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

単純に「各荷物をどのトラックに載せるか」を全探索すると、\(M^N\) 通り（最大 \(15^{15} \approx 4 \times 10^{17}\)）の組み合わせを調べる必要があり、TLEになります。

解決策：枝刈り付きバックトラッキング

以下の工夫で探索空間を大幅に削減します：

1. 重い荷物から順に処理: 重い荷物ほど配置の自由度が低いため、先に処理することで早期に矛盾を発見できます

2. トラックを容量の大きい順にソート: 大きいトラックから試すことで、成功パターンに早くたどり着きやすくなります

3. 同じ残り容量のトラックはスキップ: 残り容量が同じトラックに荷物を載せても結果は対称的なので、片方だけ試せば十分です

4. 事前チェック:

   • 最重量の荷物 > 最大容量のトラック → 絶対不可能
   • 荷物の総重量 > トラックの総容量 → 絶対不可能

アルゴリズム

1. 荷物を重さの降順でソート
2. トラックを容量の降順でソート
3. 事前チェック（不可能なケースを早期判定）
4. バックトラッキングで探索:
   - 現在の荷物を各トラックに載せることを試す
   - ただし、同じ残り容量のトラックは重複して試さない
   - 全ての荷物を載せられたら成功
   - どのトラックにも載せられなければ、前の選択に戻る

具体例で説明します： - 荷物: [5, 3, 2]、トラック容量: [6, 5] - 荷物5 → トラック1（残り1）またはトラック2（残り0） - 荷物5をトラック2に載せた場合 → 荷物3はトラック1に載せる（残り3） - 荷物2をトラック1に載せる（残り1）→ 成功！

計算量

• 時間計算量: 最悪 \(O(M^N)\) だが、枝刈りにより実際はこれよりはるかに少ない。同じ残り容量をスキップする枝刈りが特に効果的で、多くのケースで高速に動作します。

• 空間計算量: \(O(N + M)\)（荷物・トラックの情報と、各トラックの現在の積載量を保持）

実装のポイント

1. ソートの方向: 降順ソートが重要。昇順にすると枝刈りの効果が薄れます。

2. tried_capacities による重複回避:

   remaining = C[j] - loads[j]
   if remaining in tried_capacities:
      continue
   tried_capacities.add(remaining)
   

   これにより、例えば空のトラックが3台あっても、1台目に載せる場合だけを探索します。

3. バックトラック時の状態復元:

   loads[j] += weight    # 荷物を載せる
   if backtrack(item_idx + 1):
      return True
   loads[j] -= weight    # 荷物を降ろす（元に戻す）
   

   再帰から戻るときに状態を元に戻すことを忘れないようにします。

   ソースコード

def solve():
    N, M = map(int, input().split())
    W = list(map(int, input().split()))
    C = list(map(int, input().split()))
    
    # Sort trucks by capacity (descending) for better pruning
    C.sort(reverse=True)
    
    # Sort items by weight (descending) for better pruning
    items = sorted(range(N), key=lambda i: W[i], reverse=True)
    W_sorted = [W[i] for i in items]
    
    # Check if any single item exceeds maximum truck capacity
    if W_sorted and C and W_sorted[0] > C[0]:
        print("No")
        return
    
    # Check if total weight exceeds total capacity
    if sum(W) > sum(C):
        print("No")
        return
    
    # Current load of each truck
    loads = [0] * M
    
    def backtrack(item_idx):
        if item_idx == N:
            return True
        
        weight = W_sorted[item_idx]
        
        # Try to place the item in each truck
        tried_capacities = set()
        for j in range(M):
            # Skip if this truck can't hold the item
            if loads[j] + weight > C[j]:
                continue
            
            # Pruning: if we've already tried a truck with the same remaining capacity, skip
            remaining = C[j] - loads[j]
            if remaining in tried_capacities:
                continue
            tried_capacities.add(remaining)
            
            loads[j] += weight
            if backtrack(item_idx + 1):
                return True
            loads[j] -= weight
        
        return False
    
    if backtrack(0):
        print("Yes")
    else:
        print("No")

solve()

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