Overview

This problem asks us to determine whether \(N\) packages can 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 Properties

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

Issues with the Naive Approach

Simply trying all possibilities of “which truck to load each package onto” requires checking \(M^N\) combinations (up to \(15^{15} \approx 4 \times 10^{17}\)), which will result in TLE.

Solution: Backtracking with Pruning

We significantly reduce the search space with the following techniques:

1. Process heavier packages first: Heavier packages 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 a package onto trucks with identical remaining capacities yields symmetric results, so we only need to try one of them

4. Pre-checks:

   • If the heaviest package > largest truck capacity → definitely impossible
   • If total weight of packages > total truck capacity → definitely impossible

Algorithm

1. Sort packages by weight in descending order
2. Sort trucks by capacity in descending order
3. Pre-check (early detection of impossible cases)
4. Search using backtracking:
   - Try loading the current package onto each truck
   - However, don't try trucks with the same remaining capacity multiple times
   - If all packages are loaded successfully, return success
   - If the package cannot be loaded onto any truck, backtrack to the previous choice

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

Complexity

• Time complexity: Worst case \(O(M^N)\), but pruning makes the actual runtime much less than this. The pruning that skips identical remaining capacities is particularly effective, allowing fast execution in many cases.

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

Implementation Notes

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

2. Avoiding duplicates with 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 package
   if backtrack(item_idx + 1):
      return True
   loads[j] -= weight    # Unload the package (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.