概要

N個の荷物をM台のトラックに積み込むことができるかどうかを判定する問題です。各トラックには重さの合計が容量以下である限り、いくつでも荷物を積むことができます。

考察

この問題は、部分集合の分割やビンパッキング問題と呼ばれる典型的な組み合わせ最適化問題の一種です。荷物の数 \(N\) が最大で15と小さいことから、全探索による解法が現実的です。

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

最も単純な方法として、各荷物に対してどのトラックに割り当てるかを全通り試す方法があります。これは \(M^N\) 通りの組み合わせを試すことになります。しかし、\(M\) や \(N\) が15の場合、最大で \(15^{15}\) となり、非常に大きな計算量になり、現実的な時間内に解くことはできません。

改善策：DFS + 枝刈り

そこで、深さ優先探索（DFS）を用いて、荷物を1つずつトラックに割り当てていく探索を行います。ただし、そのままでは計算時間がかかりすぎるので、いくつかの枝刈りを行うことで高速化します。

枝刈りテクニック

1. 重い荷物から割り当て： 　→ 小さい荷物を先に入れてしまうと、あとで大きい荷物が入らなくなるケースが多くなります。重いものから入れることで成功率が上がります。

2. 同じ残容量のトラックはスキップ： 　→ 同じだけ余裕があるトラックに同じ荷物を入れても、結果は同じなので、探索を省略できます。

3. 全体の重さチェック： 　→ 事前にすべての荷物の合計がすべてのトラックの合計容量を超えていたら、絶対に無理なので即 No と判断できます。

アルゴリズム

1. まず、すべての荷物の重さの合計がすべてのトラックの容量の合計を超えていないかを確認します。超えていたら No を出力して終了します。

2. 荷物を重い順にソートします（枝刈りのため）。

3. 再帰的に深さ優先探索を行い、各荷物を順番に各トラックに割り当てられるか試します。

   • 各トラックについて、現在の荷重 + 今回の荷物の重さがトラックの容量以下であれば割り当て可能です。
   • 同じ「残り容量」を持つトラックはスキップして重複探索を防ぎます。

4. 最後の荷物まで割り当てられたら成功（Yes）、途中で詰まれば失敗（No）とします。

計算量

• 時間計算量: \(O(M^N)\) （最悪ケースでは指数時間かかるが、枝刈りにより実用上は十分速い）
• 空間計算量: \(O(N + M)\) （再帰の深さおよびトラック状態管理用配列）

実装のポイント

• 荷物を重い順に処理することで、早期に不可能な配置を除外できる。
• 同じ残り容量のトラックに同じ荷物を試すのは無駄なので、setを使って記録・スキップする。
• 再帰の終了条件は、すべての荷物を割り当て終わったとき（i == N）。

ソースコード

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

    # 例外処理
    if sum(W) > sum(C):
        print("No")
        return

    # 各トラックの現在の荷重
    loads = [0]*M

    # 枝刈りのため、重い荷物から割り当てを試みる
    items = sorted(enumerate(W), key=lambda x: x[1], reverse=True)
    
    def dfs(i):
        if i == N:
            return True
        idx, weight = items[i]
        seen = set()
        for j in range(M):
            if loads[j] + weight <= C[j]:
                cap = C[j] - loads[j]
                if cap in seen:
                    continue
                seen.add(cap)
                loads[j] += weight
                if dfs(i+1):
                    return True
                loads[j] -= weight
        return False

    if dfs(0):
        print("Yes")
    else:
        print("No")

if __name__ == "__main__":
    main()

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