10.19

Idea: The task is the classic Partition problem. Let S = ∑wi. If S is odd we can stop – two equal halves are impossible. Otherwise we look for a subset of the suit-cases whose weight is exactly S/2. A simple bit-set dynamic programme finds this in O(m · S) time (or O(m · S/64) with machine words) and O(S) memory.

def divide_equal(w): S = sum(w) if S & 1: # odd total return None # impossible target = S // 2 dp = [False]*(target+1) prev = [-1]*(target+1) # reconstruction array dp[0] = True for idx,weight in enumerate(w): for s in range(target, weight-1, -1): if not dp[s] and dp[s-weight]: dp[s] = True prev[s] = idx # record suitcase used to reach s if not dp[target]: return None # no subset of weight S/2 # rebuild one driver's load load1, s = [], target while s: i = prev[s] load1.append(i) # suitcase i goes to driver 1 s -= w[i] load2 = [i for i in range(len(w)) if i not in load1] return load1, load2

Explanation 1. Scan the list once, updating the 1-dimensional table dp: dp[s] is True ⇔ some subset seen so far weighs s. 2. We iterate s backwards so every suitcase is used at most once. 3. When finished, dp[S/2] tells us whether equal sharing is possible. 4. Array prev remembers which suitcase first achieved each sum, so we can trace back and list the items for the first driver; the rest automatically belong to the second. Complexities • Time = Θ(m·S) (bit-parallel ≈ m·S/word_size) • Space = Θ(S) For typical airline limits (m ≤ 50, weights ≤ 30 kg) this runs in well under a millisecond.

Back to Chapter 10