Write a C++ program called knapsack.cpp to solve the Knapsack problem. For details, read the textbook page 116~118. Your program should read the weight and value of each item from a user and determine the best subset. In the p assume that the number of items is less than 15. And also, you should assume that each item have only one. Your program should display all combinations of the item(s). However, the sequence of sets displayed on the screen is not important. rogram, you can This is a sample result of the C++ program $ gtt-o knapsack knapsack.cpp knapsack Enter a number of items: 2 Enter knapsack capacity: 5 Enter weights and values of 2 items: Item 1: Item 2: 4 10 12 set 1: set 2: set 3: set 4: --> capacity: {1} -> capacity: {2} -> capacity: {1,2} -> capacity: 0, value : $0 3, value: $12 4, value: $10 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 Item 1: 3 12 Item 2: 4 10 Enter weights and values of 2 items: capacity: 0, value: $0 set 1 set 2: {2} => capacity: 4, value: $10 set 3 1 capacity 3, value $12 set 4: {1,2} => capacity: 7 - over capacity, value: N/A => Solution: l>capacity: 3, value: $12 This is another sample run. $ g++-o 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:110 Item 3: 3 20 set 1: 11 capacity: 0, value: $0 set 2: 11 set 3: 2 set 4: 3h 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 - ove r capacity, value : N/A capacity: 2, value: $12 ->capacity: , value: $10 ->capacity: 3, value: $20 Solution: 1,3> capacity: 5, value $32