Design & Analysis of Algorithm

Problem 3. (50%) The knapsack problem is that given a set of positive integers ai,, an and napsack of size s, find a subset A of (ai,, an) such that the sum of elements in A is the largest, but at most s. Part 1. Use the dynamic programming method to design an algorithm for the knapsack pro blem. e correctness of your algorithm. Show the computational time of your algorithm carefully Part 2. Use C++ to implement the function below int knapsack( int a, //the input integers int n, //the number of input integers int s, //knapsack size int "subset, //subset elements int &size.of subset//the number of items in the subset program for the following knapsack problem: 5, 23, 27, 37, 48, 51, 63, 67, 71, 75, 79, 83, 89, 91, 101, 112, 121, 132, 137, 141, 143, Input list: 59. 171, 181, 190, 191 with knapsack size 595. Print out a subset with the sum of its elements so that the sum has the closest distance to 595. Also pi print out your source code