Overview

This problem asks us to find the minimum number of trucks required to load \(N\) items, where each truck has a maximum capacity of \(M\).

Analysis

Looking at the constraints, \(N \le 20\) is extremely small. In such cases, representing the set of items as a bitmask (a sequence of 0s and 1s) and managing all states using “bit DP” (bitmask dynamic programming) is often effective.

While there are countless combinations of how to distribute items among trucks, let us consider loading items one by one. When “the set of already loaded items \(S\)” is fixed, to optimize the subsequent loading of remaining items, it is sufficient to know only the following two pieces of information about the current state: 1. The number of trucks used 2. The current load of the truck currently being loaded (the last truck used)

If there are states with the same “number of trucks used” but a smaller “load of the last truck”, it is clearly more advantageous for loading subsequent items. Therefore, we can perform DP to minimize these two values for each subset \(S\).

Greedy approaches (such as loading items in descending order of weight) might yield a larger number of trucks in specific cases, resulting in a Wrong Answer (WA). Therefore, we search for the exact solution using DP.

Algorithm

We will use bit DP (subset DP).

We define the state dp[S] as the optimal state after loading the subset of items \(S\) onto trucks, represented as a tuple (number of trucks, load of the last truck).

For the initial state where no items are loaded, we assume the first truck is already prepared and set dp[0] = (1, 0).

From each state \(S\), we consider adding an item \(i\) that has not been loaded yet. Let \(w\) be the weight of item \(i\). - If there is enough capacity remaining in the current last truck (used + w <= M): We can load it onto the same truck. The next state will be (cost, used + w). - If there is not enough capacity: We must prepare a new truck and load it there. The next state will be (cost + 1, w).

We perform this transition for all \(S\) and \(i\). In Python, when comparing tuples, the first element (the number of trucks) is prioritized for being smaller, and if they are equal, the second element (the load) is prioritized. We can utilize this behavior to update the dp table.

Finally, the number of trucks in the state where all items are loaded, dp[(1 << N) - 1], will be the answer.

Complexity

• Time Complexity: \(O(2^N \cdot N)\)
• Space Complexity: \(O(2^N)\)

Implementation Details

• In Python, managing the state using tuples allows for a concise implementation because the state with “fewer trucks and smaller current load” is automatically prioritized as the minimum during comparisons and updates.

• Initialize the DP array with sufficiently large values (for example, (1 << 30, 0)).

• By setting the initial state dp[0] (with no items loaded) to (1, 0), we establish a state where “the first truck is prepared from the start”. This simplifies the conditional branching (whether to load the item on the same truck or a new truck) when adding an item.

  Source Code

import sys

def solve():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    W = list(map(int, input().split()))
    
    INF = (1 << 30, 0)
    dp = [INF] * (1 << N)
    dp[0] = (1, 0)
    
    for S in range(1 << N):
        cost, used = dp[S]
        if cost == (1 << 30):
            continue
        for i in range(N):
            if not (S & (1 << i)):
                w = W[i]
                if used + w <= M:
                    nxt = (cost, used + w)
                else:
                    nxt = (cost + 1, w)
                if nxt < dp[S | (1 << i)]:
                    dp[S | (1 << i)] = nxt
    
    print(dp[(1 << N) - 1][0])

solve()

---

This editorial was generated by or-glm5.2-high.