1. (30 points) Suppose you are given the knapsack problem (having knapsack capacity of 10) below. a) Work out the brute force solution using the exhaustive-search approach to this problem. Hint: Exhaustive-search leads to generating all the subsets of the set of n items given, computing the total weight of each subset in order to identify feasible subsets (i.e., the ones with the total weight not exceeding the knapsack capacity), and finding a subset of the largest value among them. b) Work out the heuristic solution using the heuristic algorithm discussed in the class. 10 = W = 7 V1 = $42 W2 = 3 V2 = $12 W3 = = 4 V3 = $40 W4 = 5 V4 = $25 = knapsack item 1 item 2 item 3 item 4