2. (points: 5+6+1) (A typical interview question) Adam wants to sell fake paintings Sun- flower to the families in N houses on a road. Adam has many copies of Sunflower with him, but each family will only buy one copy. Each family is willing to spend different amount of money on buying it. They offer to pay p1, p2, ...,pn thousand dollars respectively. The rules are: Rule (a) If Adam decides to sell a copy of Sunflower to one family, this family will surely buy it. Rule (b) The houses are in a line, numbered by 1,2,3,...,N. Adam cannot sell two copies to two adjacent families (since the adjacent families visit each other and will notice the same painting and realize it is fake). For example, he can sell it to family 1, 3 and 5, or family 1 and 4; he cannot sell it to family 2 and 3 together. Adam wants to maximize his revenue by picking the families that he sells Sunflower to. For example, for N = 3 and p = [3,8,4], the maximal revenue is 8, and is achieved when he sells Sunflower to family 2. For N=4 and p = 15, 2, 1, 4], the maximal revenue is 9, and is achieved when he sells Sunflower to family 1 and 4. Now suppose N = 6 and p= [9,7,5,9,6, 4] (this means (P1, P2, ..., p6] = [9, 7,5,9,6, 4]). Solve this problem by dynamic programming. Specify stages, states sn, decision variables In, the value function f* (sn) and its recursive relationship (Bellman equation). Identify the optimal set of families to sell Sunflower to and the optimal revenue. Remark: Read the problem statement carefully. You may lose points for missing some com- ponents required by the problem, even if your final optimal solution and optimal value are correct. If you do not use dynamical programming to solve the problem, you will get 0 point. 2. (points: 5+6+1) (A typical interview question) Adam wants to sell fake paintings Sun- flower to the families in N houses on a road. Adam has many copies of Sunflower with him, but each family will only buy one copy. Each family is willing to spend different amount of money on buying it. They offer to pay p1, p2, ...,pn thousand dollars respectively. The rules are: Rule (a) If Adam decides to sell a copy of Sunflower to one family, this family will surely buy it. Rule (b) The houses are in a line, numbered by 1,2,3,...,N. Adam cannot sell two copies to two adjacent families (since the adjacent families visit each other and will notice the same painting and realize it is fake). For example, he can sell it to family 1, 3 and 5, or family 1 and 4; he cannot sell it to family 2 and 3 together. Adam wants to maximize his revenue by picking the families that he sells Sunflower to. For example, for N = 3 and p = [3,8,4], the maximal revenue is 8, and is achieved when he sells Sunflower to family 2. For N=4 and p = 15, 2, 1, 4], the maximal revenue is 9, and is achieved when he sells Sunflower to family 1 and 4. Now suppose N = 6 and p= [9,7,5,9,6, 4] (this means (P1, P2, ..., p6] = [9, 7,5,9,6, 4]). Solve this problem by dynamic programming. Specify stages, states sn, decision variables In, the value function f* (sn) and its recursive relationship (Bellman equation). Identify the optimal set of families to sell Sunflower to and the optimal revenue. Remark: Read the problem statement carefully. You may lose points for missing some com- ponents required by the problem, even if your final optimal solution and optimal value are correct. If you do not use dynamical programming to solve the problem, you will get 0 point