Summary

This problem asks us to find the minimum number of trucks required to load all \(N\) given items into trucks with a maximum capacity of \(M\). A key feature of this problem is that the number of items \(N\) is very small, at most \(20\), which allows us to solve it efficiently using Bit DP (Dynamic Programming with bitmask).

Intuition

Why a Greedy Approach Fails

A simple greedy approach, such as “loading items into trucks in descending order of their weights,” might seem correct at first glance, but there are cases where it fails to produce the optimal solution. For example, consider a case where \(M = 10\) and the item weights are \([5, 4, 4, 3, 2, 2]\). * Greedy Approach (loading in descending order): * Truck 1: \(5 + 4 = 9\) (Remaining capacity: \(1\), cannot load any more) * Truck 2: \(4 + 3 + 2 = 9\) (Remaining capacity: \(1\), cannot load any more) * Truck 3: \(2\) * \(\Rightarrow\) A total of \(3\) trucks are required. * Optimal Solution: * Truck 1: \(5 + 3 + 2 = 10\) * Truck 2: \(4 + 4 + 2 = 10\) * \(\Rightarrow\) We can transport all items using only \(2\) trucks.

As shown above, we need to search through the combinations of items exhaustively. This is a known NP-hard problem called the “Bin Packing Problem.” However, since \(N \le 20\) is extremely small in this problem, an approach that explores all possible loading states is feasible.

Focusing on the Constraints

Note that the number of items \(N\) is very small, satisfying \(1 \le N \le 20\). The state of “which items have already been loaded onto the trucks” has \(2\) possibilities for each item: “loaded” or “not loaded.” Therefore, there are only \(2^N\) possible states in total (when \(N=20\), \(2^{20} \approx 1.05 \times 10^6\) states). Thus, we can apply Bit DP, where the set of already loaded items is represented by a bitmask.

Algorithm

We represent the set of already loaded items using the bit representation of an integer \(S\) (\(0 \le S < 2^N\)). If the \(i\)-th bit of \(S\) is 1, it means the \(i\)-th item has been loaded; if it is 0, the item has not been loaded yet.

For each state \(S\), we want to use the trucks as efficiently as possible (i.e., minimize the number of trucks used, and further maximize the remaining capacity of the current active truck). To achieve this, we store the following two pieces of information as a pair in the DP table dp[S]: 1. cnt: The number of trucks that have already been fully loaded (or cannot take more items) and dispatched. 2. used: The total weight of items loaded onto the current (last) active truck.

The optimal state is the one where “cnt is minimized, and if cnt is the same, used is minimized.”

Transitions

Consider transitioning from state \(S\) by loading a new item \(i\) that has not been loaded yet (the \(i\)-th bit of \(S\) is 0). Let the current state’s value be \((cnt, used)\). The transition falls into one of the following two patterns:

1. When the item can fit in the current truck (\(used + W_i \le M\)): The value of the new state is updated to \((cnt, used + W_i)\).
2. When a new truck is required (\(used + W_i > M\)): The current truck is dispatched, and item \(i\) is loaded onto a new truck. The value of the new state is updated to \((cnt + 1, W_i)\).

For all states \(S\), we transition to all unused items \(i\) to update the dp table. The final answer will be cnt + 1 (the number of dispatched trucks + the 1 currently active truck) in the state where all items are loaded, which is \(dp[2^N - 1]\).

Complexity

• Time Complexity: \(O(N \cdot 2^N)\) There are \(2^N\) states, and from each state, there are \(N\) transitions (choosing the next item). When \(N = 20\), the total number of transitions is \(20 \times 2^{20} \approx 2.1 \times 10^7\), which is well within the time limit.
• Space Complexity: \(O(2^N)\) The size of the DP table is \(2^N\). An array with \(2^{20}\) elements is well within the memory limit.

Key Implementation Points

In interpreted languages like Python, storing tuples (cnt, used) directly as DP elements can lead to a TLE (Time Limit Exceeded) because of the overhead of object creation and comparison.

To avoid this, the provided code compresses the two pieces of information into a single integer using bitwise operations.

• Since the maximum capacity \(M \le 10^9 < 2^{30}\), we can allocate the lower 30 bits to used and the bits above them to cnt. $\(\text{val} = (\text{cnt} \ll 30) \mid \text{used}\)$

• With this compression, comparing the values n_val < dp[next_S] naturally aligns with the prioritized comparison: “minimize cnt, and if they are equal, minimize used.” This eliminates the overhead of creating tuples or objects, ensuring high-speed execution.

  Source Code

import sys

def solve():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return
    N = int(data[0])
    M = int(data[1])
    W = [int(x) for x in data[2:]]
    
    # dp[S] = (cnt << 30) | used
    # cnt: すでに満杯になって送り出したトラックの数
    # used: 現在使用中のトラックの積載量
    LIMIT = 1 << N
    INF = 0x3fffffffffffffff
    dp = [INF] * LIMIT
    dp[0] = 0
    
    MASK = (1 << 30) - 1
    p2_W = [(1 << i, W[i]) for i in range(N)]
    
    for S in range(LIMIT):
        val = dp[S]
        cnt = val >> 30
        used = val & MASK
        for p2, w in p2_W:
            if not (S & p2):
                n_used = used + w
                if n_used <= M:
                    n_val = (cnt << 30) | n_used
                else:
                    n_val = ((cnt + 1) << 30) | w
                next_S = S | p2
                if n_val < dp[next_S]:
                    dp[next_S] = n_val
                    
    ans = (dp[LIMIT - 1] >> 30) + 1
    print(ans)

if __name__ == '__main__':
    solve()

---

This editorial was generated by gemini-3.5-flash-high.