Consider the following input for the maximum-weight independent set problem: V = {V1, V2, ..., V13} and W = {2,7,8,4,3,1, 7, 1,1,5, 1,8,6}. Use the dynamic programming algorithm to find the value of the the maximum-weight independent set. Show the array A. Use the reconstruction algorithm to obtain the maximum-weight independent set S. Show S for all iterations of the while loop. Then give the sum W(S) and its value. Solution: W [2, 7, 8, 4, 3, 1, 7, 1, 1, 5, 1, 8, 6] A [2, 7, 10, 11, 13, 13, 20, 20, 21, 25, 25, 33, 33] 13 : S 12 : S [1] 10 : S [12] 8 : S [12, 10] : S [12, 10] : S = [12, 10, 7] : S [12, 10, 7, 5] 1 : S [12, 10, 7, 5, 3] S [12, 10, 7, 5, 3, 1] W(S) 8 + 5 + 7 + 3 + 8 + 2 = 33 i i i i i i i i = 7 5 3 1. Answer the question with V = {V1, V2, ..., V17} and W = {1,9,7, 2, 2, 2,9,6,4,8,6,9,9,8, 4, 2, 4}. 2. Answer the question with V = {V1, V2, ..., V18}, and W is your CBU 899 number written twice. For example if your number is 899123456 then W = {8,9,9,1,2,3,4,5,6,8,9,9,1,2,3,4,5,6)