Consider the instance of n-4, M-15 and w[1:4] = {3, 5, 10, 12) and use the...

Transcribed Image Text:

Consider the instance of n-4, M-15 and w[1:4] = {3, 5, 10, 12) and use the SumOfSub given below to develop the tree which will be explored and how the method would apply bounding functions and actual tree which will be generated as explained in the class. Algorithm SumOfSub(s, k, r) 3 // Find all subsets of w[1: n] that sum to m. The values of a[j], // 1≤j<k, have already been determined. s = w[i] * [j] 4 // and r = = w[i]. The w[j]'s are in nondecreasing order. // It is assumed that w[1] ≤m and 5 1 w[i]> m. 6 { 7 8 1 2 9 10 11 12 13 14 15 16 17 18 19} // Generate left child. Note: s+w[k] ≤ m since Bk-1 is true. x[k] = 1; if (s+w[k] = m) then write (x[1: k]); // Subset found // There is no recursive call here as w[j]>0, 1≤j≤n. else if (s+w[k] + w[k +1] ≤m) then SumOfSub(s+w[k], k + 1, r - w[k]); // Generate right child and evaluate Bk. if ((s+r-w[k] ≥ m) and (s+w[k + 1] ≤m)) then { } x[k] := 0; SumOfSub(s, k + 1, r = w[k]); - Consider the instance of n-4, M-15 and w[1:4] = {3, 5, 10, 12) and use the SumOfSub given below to develop the tree which will be explored and how the method would apply bounding functions and actual tree which will be generated as explained in the class. Algorithm SumOfSub(s, k, r) 3 // Find all subsets of w[1: n] that sum to m. The values of a[j], // 1≤j<k, have already been determined. s = w[i] * [j] 4 // and r = = w[i]. The w[j]'s are in nondecreasing order. // It is assumed that w[1] ≤m and 5 1 w[i]> m. 6 { 7 8 1 2 9 10 11 12 13 14 15 16 17 18 19} // Generate left child. Note: s+w[k] ≤ m since Bk-1 is true. x[k] = 1; if (s+w[k] = m) then write (x[1: k]); // Subset found // There is no recursive call here as w[j]>0, 1≤j≤n. else if (s+w[k] + w[k +1] ≤m) then SumOfSub(s+w[k], k + 1, r - w[k]); // Generate right child and evaluate Bk. if ((s+r-w[k] ≥ m) and (s+w[k + 1] ≤m)) then { } x[k] := 0; SumOfSub(s, k + 1, r = w[k]); -

Answer rating: 100% (QA)

The given algorithm SumOfSub is a recursive algorithm for finding all subsets of a given set w1n tha... View the full answer