Overview

This problem asks us to determine whether \(N\) items can all be loaded onto \(M\) trucks while respecting each truck’s weight capacity limit. We solve it by combining backtracking (depth-first search) with pruning.

Analysis

Problem Characteristics

This problem is a variant of the “bin packing problem,” which is known to be NP-hard. However, due to the small constraints of \(N, M \leq 15\), we can solve it with a carefully designed exhaustive search.

Issues with the Naive Approach

Simply exhaustively searching “which truck to load each item onto” would require examining \(M^N\) combinations (up to \(15^{15} \approx 4 \times 10^{17}\)), resulting in TLE.

Solution: Backtracking with Pruning

We significantly reduce the search space with the following techniques:

1. Process heavier items first: Heavier items have less flexibility in placement, so processing them first allows us to detect contradictions early

2. Sort trucks by capacity in descending order: Trying larger trucks first makes it easier to reach successful patterns quickly

3. Skip trucks with the same remaining capacity: Loading an item onto trucks with identical remaining capacity produces symmetric results, so trying only one is sufficient

4. Preliminary checks:

   • Heaviest item > Maximum truck capacity → Absolutely impossible
   • Total weight of items > Total truck capacity → Absolutely impossible

Algorithm

1. Sort items by weight in descending order
2. Sort trucks by capacity in descending order
3. Preliminary checks (early detection of impossible cases)
4. Search with backtracking:
   - Try loading the current item onto each truck
   - However, don't try trucks with the same remaining capacity multiple times
   - Success if all items can be loaded
   - If the item can't be loaded onto any truck, backtrack to the previous choice

Let’s explain with a concrete example: - Items: [5, 3, 2], Truck capacities: [6, 5] - Item 5 → Truck 1 (remaining 1) or Truck 2 (remaining 0) - If item 5 is loaded onto Truck 2 → Item 3 goes on Truck 1 (remaining 3) - Load item 2 onto Truck 1 (remaining 1) → Success!

Complexity

• Time complexity: Worst case \(O(M^N)\), but pruning makes the actual complexity much smaller. The pruning that skips trucks with the same remaining capacity is particularly effective, allowing fast execution in many cases.

• Space complexity: \(O(N + M)\) (for storing item/truck information and the current load of each truck)

Implementation Notes

1. Sort direction: Descending sort is crucial. Ascending order would diminish the pruning effectiveness.

2. Duplicate avoidance using tried_capacities:

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

   This ensures that even if there are 3 empty trucks, we only explore loading onto the first one.

3. State restoration during backtracking:

   loads[j] += weight    # Load the item
   if backtrack(item_idx + 1):
      return True
   loads[j] -= weight    # Unload the item (restore state)
   

   Don’t forget to restore the state when returning from recursion.

Source Code

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()

This editorial was generated by claude4.5opus.