Overview

This problem asks for the minimum number of trucks required to load all items of given weights into trucks with a maximum capacity of \(M\). By leveraging the fact that the number of items \(N\) is very small (at most \(20\)), we can solve this problem efficiently using Bit DP (Dynamic Programming with bitmask).

Analysis

Limitations of the Greedy Approach

A greedy approach, such as “loading items into trucks in descending order of weight”, does not always yield the optimal (minimum) number of trucks. For example, consider a case where the maximum capacity is \(M = 10\) and the weights of the items are \([5, 4, 4, 3, 2, 2]\). - Greedy approach: Loading them in descending order of weight results in \([5, 4]\) (remaining 1), \([4, 3, 2]\) (remaining 1), and \([2]\) (remaining 8), which requires 3 trucks. - Optimal solution: If we partition them as \([5, 3, 2]\) (remaining 0) and \([4, 4, 2]\) (remaining 0), we can transport them with 2 trucks.

Thus, we need to search through all combinations of items, but the total number of ways to partition the items is extremely large.

Focusing on the Constraints

Looking at the number of items \(N\), it is very small: \(1 \leq N \leq 20\). The number of states representing whether each of the \(N\) elements is “chosen or not chosen” is \(2^N\), which is \(2^{20} \approx 10^6\) when \(N = 20\). For this number of states, Bit DP, which represents the set of already chosen items as a bitmask, is highly effective.

DP State Design

For a state \(S\) (an integer from \(0\) to \(2^N-1\)) representing “which items have been loaded”, we want to minimize the number of required trucks. However, if we only record the “number of required trucks”, we cannot determine how much weight the last truck can still carry, making it impossible to decide whether the next item can be loaded onto it.

Therefore, we store the DP value as a pair of the following two pieces of information: - dp[S] = { minimum number of trucks required, current load of the last truck }

With this definition, we can directly evaluate which state is better (more optimal) using the lexicographical comparison of std::pair. 1. A smaller number of required trucks is better. 2. If the number of trucks is the same, a smaller current load on the last truck (i.e., more remaining capacity) is better, as it makes it easier to load the next item.

Algorithm

1. Initialization:

   • Initialize all elements of the dp array with a sufficiently large value (INF).
   • Set the initial state dp[0] (where no items are loaded) to {1, 0} (representing that the first truck is waiting and empty).

2. Transitions: Let the current state be \(S\), and its DP value be cnt (number of trucks) and load (load of the last truck). Consider loading a new item \(i\) (\(0 \leq i < N\)) that is not yet in the set \(S\).

   • If it can be loaded onto the same truck (\(load + W_i \leq M\)): The number of trucks does not increase, and the load increases by \(W_i\). Transition destination: {cnt, load + W_i}
   • If a new truck is required (\(load + W_i > M\)): Add one new truck and load item \(i\) onto it. Transition destination: {cnt + 1, W_i}

Compare this candidate transition value with the already recorded dp[S | (1 << i)] and update it with the smaller (more optimal) value.

1. Outputting the Answer: The value dp[(1 << N) - 1].first, which represents the state where all items have been loaded, will be the minimum number of trucks required.

Complexity

• Time Complexity: \(O(N 2^N)\) Since there are \(2^N\) states and we try transitions to \(N\) unchosen items from each state, the total number of loop iterations is \(N 2^N\). When \(N = 20\), this requires \(20 \times 2^{20} \approx 2 \times 10^7\) operations, which easily runs within the time limit.

• Space Complexity: \(O(2^N)\) Since we maintain an array of std::pair of size \(2^N\), the memory usage is \(2^{20} \times 16 \text{ bytes} \approx 16 \text{ MB}\), keeping the space complexity sufficiently small.

Implementation Points

• Comparison of std::pair: By default, std::pair in C++ compares the first element first, and then the second element if the first elements are equal (lexicographical comparison). This perfectly aligns with our goal of “minimizing the number of trucks, and in case of a tie, minimizing the load of the last truck”. Therefore, we can update the states directly using std::min.

  Source Code

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int INF = 1e9;

int main() {
    // 高速入出力
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    long long M;
    if (!(cin >> N >> M)) return 0;

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

    // dp[S] = {必要なトラックの最小台数, 最後のトラックの現在の積載量}
    vector<pair<int, long long>> dp(1 << N, {INF, INF});
    dp[0] = {1, 0};

    for (int S = 0; S < (1 << N); ++S) {
        if (dp[S].first == INF) continue;
        for (int i = 0; i < N; ++i) {
            if (!(S & (1 << i))) {
                int next_S = S | (1 << i);
                int cnt = dp[S].first;
                long long load = dp[S].second;
                
                pair<int, long long> next_val;
                if (load + W[i] <= M) {
                    next_val = {cnt, load + W[i]};
                } else {
                    next_val = {cnt + 1, W[i]};
                }
                
                dp[next_S] = min(dp[next_S], next_val);
            }
        }
    }

    cout << dp[(1 << N) - 1].first << "\n";

    return 0;
}

---

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