1) (18 pts.) (i) Consider the following variation of the 0/1 Knapsack problem: Given are a knapsack of capacity W and n items, with each item having a profit pi, a weight w, and a type ti, 1 SiSn. There are two types: G (gold) and S (silver). The objective is to fill the knapsack not exceeding its capacity W, maximizing the profit and achieving a balanced G/S ratio. A knapsack containing k S items has a balanced G/S ratio when the number of G items is at least k and at most 2k. Describe and analyze a DP algorithm for determining the items to pack resulting in a maximum profit and fulfilling the above constraints. Address that the principle of optimality holds. State and explain the DP equations and how the entries are computed, and how the items achieving maximum profit are generated from the computed entries. Analyze time and space. (ii) You are given an integer n. Starting at 1, you are asked to generate n using the following two operations: Plusl, which increases a given number by 1, and Double2, which doubles a given number. The cost of Plusl is 1 and the cost of Double2 is 2. For exarnple, n = 21, can be generated using Plus1, Double2. Plusl, Double2. Double2, Plusl with a cost of 9. Give a DP solution generating n using operations Plusl and Double2 minimizing the total cost. Analyze your solution and explain whether it has polynomial running time