Overview

This problem asks for the minimum number of trucks required to load \(N\) items (\(N \leq 20\)) into trucks with a maximum capacity of \(M\). This is a classic “Bin Packing Problem” and can be solved using bitmask DP (dynamic programming over subsets) because \(N\) is small.

Analysis

Limitations of a Naive Approach

If we consider a naive approach of “exhaustively searching all ways to assign items to trucks”, the number of combinations becomes too large to run within the time limit. Enumerating which truck each item goes to is also difficult to handle because the number of trucks is not fixed.

Key Observation

The key constraint to notice here is \(N \leq 20\). This suggests that we can represent “which items have already been loaded” using a bitmask (\(2^N\) states).

Thus, we consider DP where the state is the “subset of items loaded”. For a subset of items \(S\), we maintain:

• The minimum number of trucks required to load the subset
• (If the number of trucks is the same) Maximize the remaining capacity of the last truck used

Why is “maximizing the remaining capacity” important? This is because the more space left in the last truck, the more likely we can load the next item without using a new truck, which is advantageous for future transitions. Since having more remaining capacity is always better when the number of trucks is the same (dominance relation), it is sufficient to maintain only this single best state for each subset.

In this DP, we load items in a way that “we fill the trucks one by one, and only the last truck is currently open”. Since any valid packing can be rearranged into a sequence where trucks are filled one by one, this strategy is guaranteed to find the optimal solution.

Algorithm

For each subset mask, we manage the state (number of trucks: trucks, remaining capacity of the last truck: space). Encoding these two values into a single integer makes comparison much simpler.

Encoding Technique

Let \(K = M + 1\), and represent the state with the following value:

\[\text{value} = \text{trucks} \times K + (M - \text{space})\]

• The first term, \(\text{trucks} \times K\), represents the number of trucks. Since \(K = M + 1\), an increase of 1 in the number of trucks always increases the value by more than the maximum possible value of the second term.
• The second term, \(M - \text{space}\), represents the “used capacity of the last truck”.

By minimizing this value, we naturally prioritize “minimizing the number of trucks first, and if the number of trucks is the same, minimizing the used capacity (which is equivalent to maximizing the remaining capacity)”.

Transitions

The initial state is set to dp[0] = M (which is \(0 \times K + M\)). This represents “0 trucks used, and 0 remaining capacity in the last truck”, ensuring that the first item loaded will automatically open a new truck.

When adding an unloaded item \(i\) (with weight \(w_i\)) to the subset mask (with current state value cur):

• If it fits in the current truck (\(w_i \leq \text{space}\)): nval = cur + wi (the number of trucks remains the same, used capacity increases by \(w_i\))
• If a new truck is required (\(w_i > \text{space}\)): nval = (trucks + 1) * K + wi (the number of trucks increases by 1, and \(w_i\) is loaded into the new truck)

If the resulting nval is smaller than dp[mask | (1 << i)], we update it.

Finally, the minimum number of trucks can be obtained by dp[full] // K (where full is the state with all items loaded).

Complexity

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

Since \(N \leq 20\), the number of operations is around \(2^{20} \times 20 \approx 2 \times 10^7\), which runs well within the time limit.

Implementation Points

• Encoding two values into a single integer is the core of this implementation. By using \(K = M+1\) as the base, we can easily retrieve the values as trucks = cur // K and used capacity = cur % K. Furthermore, a simple comparison of these single integer values simultaneously optimizes both “prioritizing the number of trucks” and “maximizing the remaining capacity”.

• By setting the initial state to “0 remaining capacity”, the code is designed so that the first item automatically opens a new truck, making the conditional branching very simple.

• Since it is guaranteed that each item has a weight \(W_i \leq M\), any individual item can always be loaded into some truck (preventing issues like infinite loops or items that cannot be packed).

  Source Code

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0]); M = int(data[1])
    w = [int(data[2 + i]) for i in range(n)]
    full = (1 << n) - 1
    K = M + 1
    INF = float('inf')
    size = 1 << n
    dp = [INF] * size
    # encode value = trucks * K + (M - space)  (minimize)
    dp[0] = M  # 0 trucks, space 0
    for mask in range(size):
        cur = dp[mask]
        if cur == INF:
            continue
        trucks = cur // K
        space = M - (cur % K)
        next_truck_base = (trucks + 1) * K
        for i in range(n):
            if not (mask >> i) & 1:
                wi = w[i]
                if wi <= space:
                    nval = cur + wi
                else:
                    nval = next_truck_base + wi
                nm = mask | (1 << i)
                if nval < dp[nm]:
                    dp[nm] = nval
    print(dp[full] // K)

main()

---

This editorial was generated by claude4.8opus-high.