Overview

This is a problem where you need to transport \(N\) items using an elevator, grouping them so that the total weight does not exceed the weight limit \(C\), and finding the minimum number of round trips required.

Analysis

This problem is an optimization problem: “How many trips are needed to transport all the items?” A naive approach might be a greedy method (e.g., packing items starting from the heaviest), but since the number of items \(N\) is at most \(15\), exhaustive search is feasible, making an exact solution the reliable approach.

A key observation is that the selection of items (i.e., which items to transport together) can be represented using bitsets (bitmasks). For example, if there are \(4\) items, the set \(\{0, 2\}\) means selecting the \(0\)-th and \(2\)-nd items.

The basic strategy for exhaustive search is as follows: 1. For all subsets of items, precompute whether their total weight is at most \(C\). 2. Perform dynamic programming (DP) with the set of already transported items as the state, and find the minimum number of round trips.

This approach of exhaustively searching combinations of subsets can be realized using “subset enumeration + DP”.

Algorithm

For this problem, we use dynamic programming with bitmasks (bit DP).

Steps

1. Preprocessing: For all subsets, determine whether the total weight of the items in that subset is at most \(C\), and list the valid subsets.
2. DP Definition:
   • dp[mask] := the minimum number of round trips when the set of already transported items is mask
   • Initial value: dp[0] = 0 (no items transported yet), all others are infinity
3. DP Transition:
   • For the current state mask, compute the set of unused items unused.
   • For all subsets of unused (excluding the empty set), if the subset is valid (total weight \(\leq C\)), transition with new_mask = mask | subset:

     
     dp[new_mask] = min(dp[new_mask], dp[mask] + 1)
     

4. Answer: dp[(1 << N) - 1] is the final minimum number of round trips.

Concrete Example

For example, with \(N=3\), \(C=10\), and items [3, 5, 7]: - Each item can be transported individually, \(\{3, 5\}\) is OK, but \(\{5, 7\}\) is NG. - The optimal way is: trip 1 transports \(\{3, 5\}\), trip 2 transports \(\{7\}\) → 2 trips total.

Complexity

• Time complexity: \(O(3^N)\)
  • Enumerating subsets of the remaining items for each state takes \(O(2^{N})\) per operation, but the total across all states is \(O(3^N)\) (a well-known result for subset enumeration).
• Space complexity: \(O(2^N)\)
  • The size of the DP table is \(2^N\)

Implementation Notes

• You need to handle subsets properly using bit operations.

• The idiom for “enumerating all subsets of a given set” appears frequently, so it’s useful to remember that it can be written as follows:

  
  submask = unused
  while submask > 0:
    # Some processing
    submask = (submask - 1) & unused
  

• Instead of computing the total weight every time, you can speed things up by precomputing valid subsets during preprocessing (the current code computes it each time, so consider a preprocessing version if needed).

  Source Code

from itertools import combinations

def main():
    N, C = map(int, input().split())
    W = list(map(int, input().split()))
    
    # 全ての部分集合について、その和がC以下かどうかを前計算
    valid_subsets = []
    for mask in range(1 << N):
        total = 0
        subset = []
        for i in range(N):
            if mask & (1 << i):
                total += W[i]
                subset.append(i)
        if total <= C:
            valid_subsets.append((mask, total))
    
    # dp[mask] := 使用した荷物の集合がmaskであるときの最小往復回数
    INF = float('inf')
    dp = [INF] * (1 << N)
    dp[0] = 0
    
    # 各状態に対して、有効な部分集合を加えた新しい状態に遷移
    for mask in range(1 << N):
        if dp[mask] == INF:
            continue
        # まだ使っていない荷物の集合
        unused = ((1 << N) - 1) ^ mask
        # unusedの部分集合をすべて試す（空集合は除く）
        submask = unused
        while submask > 0:
            # submaskがvalidかチェック
            is_valid = False
            total_weight = 0
            for i in range(N):
                if submask & (1 << i):
                    total_weight += W[i]
            if total_weight <= C:
                is_valid = True
            
            if is_valid:
                new_mask = mask | submask
                dp[new_mask] = min(dp[new_mask], dp[mask] + 1)
            
            submask = (submask - 1) & unused
    
    print(dp[(1<<N)-1])

if __name__ == "__main__":
    main()

This editorial was generated by qwen3-coder-480b.