Design & Analysis of Algorithms

Problem 3. (50%) The knapsack problem is that given a set of positive integers {a1,, an), and a knapsack of size s, find a subset A of a1,, an) such that the sum of elements in A is the largest, but at most s Part 1. 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 Test your program for the following knapsack problem: Input list: 5, 23, 27, 37, 48, 51, 63, 67, 71, 75, 79, 83, 89, 91, 101, 112, 121, 132, 137, 141, 143, 147, 153, 159, 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 print out your source code. Problem 3. (50%) The knapsack problem is that given a set of positive integers {a1,, an), and a knapsack of size s, find a subset A of a1,, an) such that the sum of elements in A is the largest, but at most s Part 1. 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 Test your program for the following knapsack problem: Input list: 5, 23, 27, 37, 48, 51, 63, 67, 71, 75, 79, 83, 89, 91, 101, 112, 121, 132, 137, 141, 143, 147, 153, 159, 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 print out your source code