For example, suppose that we are given a knapsack of weight 20 and five items of weights 11, 8, 7, 6, and 5. Then, a solution to the problem would be items 2, 3, and 5, whose total weight 8 + 7 + 5 = 20.
Implement a solution to the knapsack problem using the "search with backtracking" strategy described in class for depth-first search and the n-Queens problem. Use the following function header:
int knapSack(int items, int target)The int array items contains the weights of the given items. The int parameter target gives the target weight permitted in the knapsack. The function should return an array of item weights that fit exactly in the given knapsack.
It is quite possible that you may need additional parameters just to control the recursion. In that case, use the above function header for a "wrapper" function and define a function called recursiveKnapSack.
11 4 8 3 17 1 9 19 20 27 5 7
Note: You will be asked to solve this problem on the quiz with some other sequence of numbers as input. So it is worth your time to try and answer this question without running the code.
Repeat the above experiments for input generated as described below. Generate each size-n integer array in the following manner. Start by assigning the integer i to slot i in the array. Thus the array starts off with entries 0, 1, 2, ..., n-1 in that order. Then do the following 20 times: pick a pair of indices i and j, at random, in the range [0, n-1], and swap the elements in slots i and j. After this is done, we may no longer have a sorted array, but the array will still be "almost sorted''. Our expectation for "almost sorted'' inputs is that quickSort should run in O(n^2) and will clearly be slower than randomizedQuickSort, which runs in O(n log(n)) time, on an average, independent of the type of input.