Overview

This problem asks for the minimum number of trucks required to load \(N\) items (with weights \(W_i\)) onto trucks with a maximum capacity of \(M\). This is the minimization version of the well-known “Bin Packing Problem”.

Analysis

Naively, one might consider trying all possible ways to assign each item to a truck. However, since the number of trucks is also variable, the number of assignment combinations is extremely large, and a simple brute-force search will fail.

The key here is the constraint \(N \leq 20\). Since \(N\) is small, we can represent the subset of items already loaded using an \(N\)-bit bitmask. Since \(2^{20} \approx 10^6\), we have plenty of time and space to keep all subsets as states.

Now, we want to find the “minimum number of trucks” for each subset of items, but keeping track of only the number of trucks is not enough. This is because we need to know how much capacity is left in the current truck.

Therefore, we maintain the state as a pair of the following two values:

• The number of trucks used (including the current/last one)
• The total weight already loaded onto the last (current) truck

With these two values, when we add a new item, we can determine whether “it fits in the current truck” or “we need to use a new truck”.

If there are multiple states that achieve the same subset of items, we only need to keep the single best state according to the following priority (lexicographically smallest):

1. First, a smaller number of trucks is preferred.
2. If the number of trucks is the same, a smaller total weight loaded on the last truck is preferred (as this leaves more remaining capacity, making it easier to load future items).

This comparison is valid because a state with the same number of trucks but more remaining capacity can do everything that a state with less remaining capacity can do.

Algorithm

We perform dynamic programming using bitmasks.

• dp[mask] = the lexicographically smallest pair of (number of trucks, weight loaded on the last truck)
• Initial state: dp[0] = (1, 0) (even with 0 items, we consider 1 truck to be prepared)

For the transition, we choose an item \(i\) that has not been loaded yet, and transition from the current state \((g, r)\) as follows:

• If \(r + W_i \leq M\) (fits in the current truck): The new state is \((g,\; r + W_i)\)
• Otherwise (does not fit, so we use a new truck): The new state is \((g+1,\; W_i)\)

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

The number of trucks in the state dp[full] (where full = (1<<N) - 1), representing all items loaded, is the answer.

As a concrete example, consider \(M = 10\) and items \(\{6, 4, 5, 5\}\). Since they can be divided into two trucks as \(\{6, 4\}\) and \(\{5, 5\}\), the answer is \(2\). The DP automatically searches for such packing configurations by adding items one by one.

Complexity

• Time Complexity: \(O(2^N \cdot N)\)
  • For each mask (\(2^N\) possibilities), we try \(N\) candidate items to add. For \(N=20\), this requires about \(2 \times 10^7\) operations, which is well within the time limit.
• Space Complexity: \(O(2^N)\)
  • The size of the dp array is \(2^N\).

Implementation Details

• Since the maximum capacity \(M\) and the sum of weights can be up to \(10^9 \times 20 = 2 \times 10^{10}\), the weight and capacity should be handled using 64-bit integers (long long).

• By using the default lexicographical comparison of pair<int, long long>, “prioritize the number of trucks, and compare the loaded weight in case of a tie” is naturally achieved, making the implementation concise.

• We can skip unreachable states (where the number of trucks is INT_MAX) to avoid redundant transitions. Note that since the initial state is set to dp[0] = (1, 0), as long as the number of items is non-zero, the correct number of trucks will be found in the end (which is fine since \(N \geq 1\) by constraints).

  Source Code

#include <bits/stdc++.h>
using namespace std;

int main(){
    int N; long long M;
    cin >> N >> M;
    vector<long long> w(N);
    for(int i=0;i<N;i++) cin >> w[i];
    
    int full = (1<<N) - 1;
    // dp[mask] = (groups, used in last group), minimize groups then used
    vector<pair<int,long long>> dp(1<<N, {INT_MAX, 0});
    dp[0] = {1, 0};
    for(int mask=0; mask<(1<<N); mask++){
        if(dp[mask].first == INT_MAX) continue;
        auto [g, r] = dp[mask];
        for(int i=0;i<N;i++){
            if(mask & (1<<i)) continue;
            int nmask = mask | (1<<i);
            pair<int,long long> cand;
            if(r + w[i] <= M){
                cand = {g, r + w[i]};
            } else {
                cand = {g+1, w[i]};
            }
            if(cand < dp[nmask]) dp[nmask] = cand;
        }
    }
    cout << dp[full].first << "\n";
    return 0;
}

---

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