Overview

This problem asks us to find the minimum number of trucks of capacity \(M\) required to load \(N\) items.

Since \(N \leq 20\) is small, we can solve this using bitmask DP, where the set of items is represented by a bitmask.

Analysis

This is a problem of “distributing all items into bins with a capacity limit” (the Bin Packing Problem).

If we simply use brute force to decide which truck each item goes into, the number of combinations becomes extremely large and will not run in time even for \(N=20\).

Also, a greedy approach such as “loading as much as possible in order” is incorrect.

As an example, consider the case where \(M=10\) and the items are \(6,6,4,4\).

If we load them in order:

• 1st truck: \(6\)
• 2nd truck: \(6+4=10\)
• 3rd truck: \(4\)

This requires 3 trucks.

However, the optimal solution is:

• 1st truck: \(6+4=10\)
• 2nd truck: \(6+4=10\)

which only requires 2 trucks.

Therefore, we need to efficiently explore all combinations.

Since \(N \leq 20\), we can represent the set of items using a bitmask.

For each set, we maintain:

• The minimum number of trucks needed to carry the items in the set
• The weight loaded on the last truck at that time

The key insight is that if the number of trucks is the same, “the smaller the weight used in the last truck, the better”.

For example, even if we use 2 trucks in both cases, having a weight of \(5\) on the last truck makes it easier to add other items later compared to having a weight of \(9\).

Algorithm

Let the bitmask \(mask\) represent the “set of items that have already been loaded”.

We define \(dp[mask]\) as follows:

\(dp[mask] = (a, b)\)

• \(a\): The minimum number of trucks required to carry the items in \(mask\)
• \(b\): The minimum total weight of the items loaded on the last truck at that time

The initial state is:

\(dp[0] = (1, 0)\)

This can be interpreted as “we have prepared 1 empty truck and have not loaded anything yet”.

Next, for each \(mask\), we try all possible items \(i\) to be added last.

If item \(i\) is included in \(mask\), let

\(prev = mask \setminus \{i\}\)

In other words, \(prev\) is the set obtained by removing item \(i\) from \(mask\).

We start from the state of \(dp[prev]\).

If we can add item \(i\) to the last truck, which means

\(b + W_i \leq M\)

we load it onto the same truck.

In this case, the state becomes:

\((a, b + W_i)\)

On the other hand, if it cannot be loaded onto the last truck, we must use a new truck.

In this case, the state becomes:

\((a+1, W_i)\)

We try this for all \(i\) and choose the best one based on the following priority:

1. Fewer trucks used
2. If the number of trucks is the same, the smaller weight on the last truck

The final answer is the number of trucks in:

\(dp[(1 << N) - 1]\)

Complexity

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

Since \(N \leq 20\), \(2^N\) is at most about \(10^6\), which is well within the time limit.

Implementation Details

• We check if the \(i\)-th bit of \(mask\) is set to determine if item \(i\) is included in the set.

• We can create the set obtained by removing item \(i\) from \(mask\) using mask ^ (1 << i).

• Since the weight \(W_i\) and capacity \(M\) can be up to \(10^9\), we should use long long.

• By setting dp[0] = {1, 0}, we can process the first item using the same transition rules.

  Source Code

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    long long M;
    cin >> N >> M;

    vector<long long> W(N);
    for (int i = 0; i < N; i++) cin >> W[i];

    int total = 1 << N;
    const int INF = 1e9;

    vector<pair<int, long long>> dp(total, {INF, 0});
    dp[0] = {1, 0};

    for (int mask = 1; mask < total; mask++) {
        pair<int, long long> best = {INF, 0};

        for (int i = 0; i < N; i++) {
            if (!(mask & (1 << i))) continue;

            auto cur = dp[mask ^ (1 << i)];

            if (cur.second + W[i] <= M) {
                cur.second += W[i];
            } else {
                cur.first++;
                cur.second = W[i];
            }

            if (cur.first < best.first ||
                (cur.first == best.first && cur.second < best.second)) {
                best = cur;
            }
        }

        dp[mask] = best;
    }

    cout << dp[total - 1].first << '\n';

    return 0;
}

---

This editorial was generated by gpt-5.5-high.