Write a C++ (or Java) program named hw4_1.cpp Your program should read the weight and value of each item from a user and determine the best subset. In the homework, you can assume that the number of items is less than 15. Also, you should assume that each item has only one Input format: This is a sample input from a user. 2 5 3 12 4 10 1 The first line (= 2 in the example) is the number of items for the knapsack problem. The second line = 5 in the example) is the knapsack capacity. After that, the two following lines indicate the capacity and value of each item. For instance, the third line = 3 12) indicates that the first item's capacity is 3 and its value is 12. The last line = 4 10) indicates that the second item's capacity is 4 and its value is 10. Sample Run 0: Assume that the user typed the following lines 2 5 3 12 4 10 This is the correct output of your program. Item: 1 Capacity: 3 Value:12 Note that we can have 4 different combinations with the two items like below, and the solution is the combination 2. Combination 1: No item. Its capacity is O and value is 0. Combination 2: Item 1. Its capacity is 3 and value is 12. Combination 3: Item 2. Its capacity is 4 and value is 10. Combination 4: Item 1 and 2. Its capacity is 7 which is over capacity. Sample Run 1: Assume that the user typed the following lines 3 5 2 12 1 10 3 20 This is the correct output of your program. Item: 1 3 Capacity: 5 Value: 32 In this case, there are 8 different combinations with the three items like below. Combination 1: No item Its capacity is O and value is 0. Combination 2: Item 1. Its capacity is 2 and value is 12. Combination 3: Item 2. Its capacity is 1 and value is 10. Combination 4: Item 3. Its capacity is 3 and value is 20. Combination 5: Item 1 and 2. Its capacity is 3 and value is 22. Combination 6: Item 2 and 3. Its capacity is 4 and value is 30. Combination 7: Item 1 and 3. Its capacity is 5 and value is 32. Combination 8: Item 1, 2, and 3. Its capacity is 6 which is over capacity When you display the result, the sequence of items is important. If the number of items in the solution is more than one, they should be displayed in ascending order. For example, your program should display the items in the sequence of 1 3" as the example. If your program displays it -3 1", this is not a correct result Sample Run 2: Assume that the user typed the following lines 4 5 2 30 3 40 2 30 3 40 This is the correct output of your program. Item: Multiple solutions Capacity: 5 Value: 70 Note that the correct item in the sample input displays "Multiple solutions" because there is more than one solution (= 2 or more combinations) to the knapsack problem Write a C++ (or Java) program named hw4_1.cpp Your program should read the weight and value of each item from a user and determine the best subset. In the homework, you can assume that the number of items is less than 15. Also, you should assume that each item has only one Input format: This is a sample input from a user. 2 5 3 12 4 10 1 The first line (= 2 in the example) is the number of items for the knapsack problem. The second line = 5 in the example) is the knapsack capacity. After that, the two following lines indicate the capacity and value of each item. For instance, the third line = 3 12) indicates that the first item's capacity is 3 and its value is 12. The last line = 4 10) indicates that the second item's capacity is 4 and its value is 10. Sample Run 0: Assume that the user typed the following lines 2 5 3 12 4 10 This is the correct output of your program. Item: 1 Capacity: 3 Value:12 Note that we can have 4 different combinations with the two items like below, and the solution is the combination 2. Combination 1: No item. Its capacity is O and value is 0. Combination 2: Item 1. Its capacity is 3 and value is 12. Combination 3: Item 2. Its capacity is 4 and value is 10. Combination 4: Item 1 and 2. Its capacity is 7 which is over capacity. Sample Run 1: Assume that the user typed the following lines 3 5 2 12 1 10 3 20 This is the correct output of your program. Item: 1 3 Capacity: 5 Value: 32 In this case, there are 8 different combinations with the three items like below. Combination 1: No item Its capacity is O and value is 0. Combination 2: Item 1. Its capacity is 2 and value is 12. Combination 3: Item 2. Its capacity is 1 and value is 10. Combination 4: Item 3. Its capacity is 3 and value is 20. Combination 5: Item 1 and 2. Its capacity is 3 and value is 22. Combination 6: Item 2 and 3. Its capacity is 4 and value is 30. Combination 7: Item 1 and 3. Its capacity is 5 and value is 32. Combination 8: Item 1, 2, and 3. Its capacity is 6 which is over capacity When you display the result, the sequence of items is important. If the number of items in the solution is more than one, they should be displayed in ascending order. For example, your program should display the items in the sequence of 1 3" as the example. If your program displays it -3 1", this is not a correct result Sample Run 2: Assume that the user typed the following lines 4 5 2 30 3 40 2 30 3 40 This is the correct output of your program. Item: Multiple solutions Capacity: 5 Value: 70 Note that the correct item in the sample input displays "Multiple solutions" because there is more than one solution (= 2 or more combinations) to the knapsack