Write Algorithm Uses Dynamic Program Find Solution Knapsack Problem Input Capacity Knapsac Q37265625

Write an algorithm that uses dynamic program to find a solutionto the knapsack problem.

The input is the capacity of the knapsack then each row of thetable of values and weights.

The output is the resulting maximum value of the items that canbe put in the knapsack.

Code submitted in C++

Sample Input 1:

111 16 218 522 628 7

Sample Output 1:

40

Sample Input 2:

815 110 59 35 4

Sample Output 2:

29

Sample Input 3:

51 12 13 14 15 1

Sample Output 3:

15

Sample Input 4:

51 12 13 14 5

Sample Output 4:

6

Sample Input 5:

51 12 13 110 5

Sample Output 5:

10

Sample Input 6:

510 51 12 13 1

Sample Output 6:

10

---

Answer

---

CODE

#include