Answer Happy

Question: Backtracking and Branch-and-Bound [25 Points] Consider the following backtracking algorithm for solving the 0-1 Knapsack Problem: Backtracking_Knapsack (val, wght, Cn) Create two arrays A1 and A2 each of size n and initialize all of their entries to zeros Initialize the attributes takenVal, untakenVal and takenWght in each of A1 and A2 to zero totValSum = 0 for i = 1 ton Output totalSum + valli Find Solutions (1) Print: Contents of A1 l/prints the actual contents of A1 Print: Contents of A2 I/prints the actual contents of A2 Find Solutions (1) 1 if (A1.takenWght >C) Print: Backtrack at i Iſprints actual value of i return 4 if (n+1) Print: Check leaf with soln A1 l/prints actual content of A1 if (A1.takenVal > A2 takenVal) Print: Copy A1 into A2 liprints actual array contents Copy A1 into A2 5 6 GOOD return 10 Dont Takeltem(A1, i) 11 Find Solutions (i+1) 12 Takeltem(A1, i) 13 Find Solutions (i+1) 14 UndoTakeltem(1,1) val is array of values, wght is array of weights, C is knapsack capacity and n is number of items. (a) Show next to the above code the output that it prints for the following input instance: Item 1: weight = 7 Kg, value = $8 Item 2: weight = 2 kg, value = 53 Item 3: weight = 5 kg, value = $6 Capacity = 10 Assume that each print statement appears on a separate line in the output and prints the contents of each array as a bit string. For example, the print statement on Line 7 of Find Solutions() may print something like this: Copy 101 into 001. (10 points)

(b) In Assignment 4, you have implemented a Branch-and-Bound (B&B) algorithm for this problem using the following three upper bounds: UB1: Sum the values of taken items and undecided items UB2: Sum the values of taken items and the undecided items that fit in the remaining capacity UB3: Sum the values of taken items and the solution to the remaining sub-problem solved as a Fractional knapsack problem. Given the following instance of the problem, Enter in the table below the value of each of the above bounds at each of the nodes specified in the table. Each row specifies a tree node, and the items that are not mentioned in that row have not been decided yet at that node. (9 points) Item 1: weight = 3 Kg, value = $24 Item 2: weight = 4 kg, value = $20 Item 3: weight = 5 kg, value = $15 Item 4: weight = 9 kg, value = $18 Item 5: weight = 7 kg, value = $7 Capacity = 15 Node UB1 UB2 UB3 Item 1 not taken Item 1 taken and Item 2 not taken Item 1 taken and Item 2 taken (c) Assuming that k backtrackings happen on Line 2 at the same level i, give a mathematical formula that expresses the number of pruned nodes p as a function of i, k and the number of items n. For example, each backtracking at i-n will prune 2 nodes, and each backtracking at i=n-1 will prune 6 nodes, and so forth (draw a little tree to verify this). Give an algebraic formula for p as a function of i, k and n. (6 points)