Overview

Given \(N \le 15\) items, we need to find the minimum number of round trips (groups) required to transport them, where each trip can carry items with total weight at most \(C\).

Analysis

This problem is essentially a bin packing problem: “divide items into groups such that each group’s total weight is at most \(C\).” While this is generally a hard problem, since \(N \le 15\) is small, DP over all subsets is feasible.

Naively enumerating all possible groupings would result in an explosive number of partitions (on the order of Bell numbers), which is impractical even for \(N=15\). Additionally, greedy approaches (such as packing heaviest first) cannot guarantee optimal solutions and will result in WA.

Instead, we manage “which items have been transported so far” using a bitmask (subset), and optimize (number of round trips, weight loaded on the current trip) via DP, solving it with \(2^N\) states.

The key insight is that while we want to minimize the number of round trips, when the number of trips is the same, having a smaller current load is more advantageous since it leaves more room for future items. Therefore, we compare states using lexicographical order: - Minimize the number of round trips first - If equal, minimize the current load

Algorithm

State

Let \(mask\) represent the “set of items that have been transported” (\(N\) bits).

DP array: - \(dp[mask] = (r, s)\) - \(r\): number of round trips (trips) used so far - \(s\): total weight loaded on the last trip (the trip currently being used)

We maintain the lexicographically smallest \((r, s)\).

Initial state: - \(dp[0] = (1, 0)\) Nothing has been transported yet, but thinking of it as “about to start loading the 1st trip” simplifies the transitions.

Transitions

For each \(mask\), consider adding one item \(i\) that hasn’t been transported yet.

• If \(s + W_i \le C\), it fits on the same trip:
  • Candidate for \(dp[mask \cup \{i\}]\) is \((r, s + W_i)\)
• Otherwise, start a new trip:
  • Candidate is \((r + 1, W_i)\)

Perform this for all \(mask\) and all \(i\), updating with the minimum.

Example (Illustration)

With \(C=10\) and items \([6,5,4]\): - First, load \(6\): current trip has weight \(6\) - Next, \(5\) gives \(6+5=11\) which exceeds the limit, so start a new trip with \(5\) - Then load \(4\): \(5+4=9\) fits - Result: transportable in 2 trips.

By keeping track of “the current trip’s load \(s\),” we can correctly manage “what else can fit on the same trip.”

Complexity

• Time complexity: \(O(N \cdot 2^N)\) For each \(mask\) (\(2^N\) total), we try adding up to \(N\) items.
• Space complexity: \(O(2^N)\) The \(dp\) array holds \(2^N\) states.

Implementation Notes

• In Python, tuples are compared lexicographically, so writing cand < dp[nmask] naturally selects “fewer round trips first, then smaller load if tied.”

• A key trick is setting the initial value to dp[0] = (1, 0) (starting the trip count from 0 would require additional case handling).

• The final answer is dp[(1<<N)-1][0] (the number of round trips in the state where all items have been transported).

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N, C = map(int, input().split())
    W = list(map(int, input().split()))
    M = 1 << N

    INF = 10**18
    dp = [(INF, INF)] * M
    dp[0] = (1, 0)

    for mask in range(M):
        rides, load = dp[mask]
        for i in range(N):
            if mask & (1 << i):
                continue
            nmask = mask | (1 << i)
            if load + W[i] <= C:
                cand = (rides, load + W[i])
            else:
                cand = (rides + 1, W[i])
            if cand < dp[nmask]:
                dp[nmask] = cand

    print(dp[M - 1][0])

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.