Create a C++ program that solves this common knapsack problem, all subsets need to be listed, and the output should be equal to the picture above.

$ g+t-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: 1 10 Item 3: 3 20 capacity: capacity: capacity: capacity: 0, 2, 1, 3, value: value: value: value: $0 $12 $10 $20 set 1: h set 2: 1 set 3 12 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 $ g+t-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: 1 10 Item 3: 3 20 capacity: capacity: capacity: capacity: 0, 2, 1, 3, value: value: value: value: $0 $12 $10 $20 set 1: h set 2: 1 set 3 12 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