Write a C++ program called knapsack.cpp to solve the Knapsack problem. Your program should read the weight and value of each item from a user and determine the best subset. In the program, you can assume that the number of items is less than 15. And also, you should assume that each item have only one. To get the full credits, your program should display all combinations of the item(s). However, the sequence of sets displayed on the screen is not important. [Hint: You can use the problem 5 of the homework 3, equal group.cpp, to solve the problem.] This is a sample result of the C++ program on the cloud9 $ gtt- knapsack knapsack.cpp $ . /knapsack Enter a number of items 2 Enter knapsack capacity: 5 Enter weights and values of 2 items: Item 1: 3 12 Item 2: 4 10 ->capacity: 0, value: $0 set 1: set 2: l capacity 3, value: $12 set 3: {2} => capacity: 4, value: $10 set 4: 1,2capacity:7- over capacity, value N/A Solution: {1} => capacity: 3, value: $12 In the same run, the sequence of sets is not important. For example, if your program displays like below, this is fine as well Enter a number of items 2 Enter knapsack capacity: 5 Enter weights and values of 2 items: Item 1: 3 12 Item 2: 10 capacity: 0, value: $0 set 1: set 2: 2 capacity: 4, value $10 set 3: 1)-> capacity: 3, value: $12 set 4: 1,2capacity:7- over capacity, value N/A Solution: {1} -> capacity: 3, value: $12 This is another sample run $ gtt- knapsack knapsack.cpp $ ./knapsack Enter a number of items: 3 Enter knapsack capacity: 5 Enter weights and values of 3 items: Item 1: 2 12 Item 2: 1 10 Item 3: 3 20 capacity: capacity: capacity: capacity: 0, 2, 1, 3, value: value: value: value: $0 $12 $10 $20 set 1: set 2: 1 set 3 (2) set 4: 3 set 5: 1,2) -> capacity: 3, value $22 set 6: {2,3} => capacity: 4, value: $30 set 7: 1,3) ->capacity: 5, value $32 set 8: {1,2,3} -> capacity: 6 - over capacity, value: N/A -> => -> Solution: {1,3} => capacity: 5, value: $32