1 answer
Solutions: {3, 8, 9}, {5, 7, 8} and {5, 15}, i.e. x = (1,0,0,1,1,0), (0,1,1,1,0,0) and (0,1,0,0,0,1).
Given \(n = 6\), \(W = \{3, 5, 7, 8, 9, 15\}\) (already in ascending order), \(M = 20\). Total \(r = 3+5+7+8+9+15 = 47\).
Approach (backtracking): decide for each weight in order whether to include it (\(x_k = 1\)) or not (\(x_k = 0\)). Keep \(s\) = sum of chosen weights and \(r\) = sum of the remaining weights. A node is killed (bounded) if
- \(s + w_{k+1} > M\) (even the next smallest weight overshoots), or
- \(s + r < M\) (even taking all remaining weights cannot reach M).
Tracing the search (depth first, include before exclude):
- 3, 5, 7 → s = 15; adding 8 gives 23 > 20, killed. 3, 5, 8 → 16; 3, 5, 9 → 17; next weight overshoots. Dead ends.
- 3, 7, 8 → 18; 3, 7, 9 → 19: dead ends.
- 3, 8, 9 → s = 20 = M. Solution 1: {3, 8, 9}.
- Exclude 3: 5, 7, 8 → s = 20. Solution 2: {5, 7, 8}.
- 5, 15 → s = 20. Solution 3: {5, 15}.
- Excluding both 3 and 5: the remaining weights {7, 8, 9, 15} have no subset with sum 20, so the search ends.
Algorithm (initial call SumOfSub(0, 1, 47), with weights sorted and \(w_1 \le M\)):
SumOfSub(s, k, r):
// s = sum of w[1..k-1] chosen, r = w[k] + ... + w[n]
x[k] = 1 // left child: include w[k]
if s + w[k] == M:
print x[1..k] // a subset found
else if s + w[k] + w[k+1] <= M:
SumOfSub(s + w[k], k + 1, r - w[k])
// right child: exclude w[k]
if (s + r - w[k] >= M) and (s + w[k+1] <= M):
x[k] = 0
SumOfSub(s, k + 1, r - w[k])
Check: 3 + 8 + 9 = 20, 5 + 7 + 8 = 20, 5 + 15 = 20. Worst-case time is \(O(2^{n})\), but bounding prunes most of the state-space tree.
Your answer
Log in or create a free account to answer this question.