Problem 1. (70 scores) Consider the binary knapsack problem x1,x2,,x5maximizes.t.9x1+12x2+8x3+5x4+12x56x1+7x2+5x3+4x1+8x517x1,x2,x3,x4,x5{0,1}. Solving this problem exactly gives the optimal solution of x1=x2=x4=1,x3=x5=0 and the optimal value of 26. Please also solve this problem using the two greedy methods that we introduced in the lecture note, and compare the solutions returned by greedy methods to the optimal solution