3. (5 points) Write a program in C++ to find the optimal solution of the knapsack problem. For this, Step 1. In the main function, read the input from a file input.txt which has the following format:

7

20

1 1

2 3

3 5

4 5

5 8

6 9

9 10

The first number specifies the number of items, the second number specifies the capacity of the knapsack, and then the next two numbers respectively specify the weight and value of the first item, and so on. Read the first number in a variable n, the second number in a variable W, and then dynamically create two arrays w and v of dimension n + 1, and then store the weight and value of item i in w[i] and v[i] (ignore the index 0). Also, dynamically create a 2-dimensional array Sol of dimension (n + 1) (W + 1) to store the actual solution (ignore the index 0).

Step 2. Implement the following function prototype: int Knapsack(int *v, int *w, int j, int cap, int **Sol) which takes the input v, w, the first j items, and capacity cap of knapsack, and outputs the optimal value that can be taken in the Knapsack of size cap from the first j items. Also, store the binary information in Sol[j][cap] whether the item j is picked or not. (HINT: Use the recursive algorithm to solve this.)

Step 3. Call the function Knapsack from main with the input read from the file, and prints the optimal solution as follows:

Optimal value: 30

Items to pick: 2 3 4 5 6