Assignment #9, COP-3337

THIS ASSIGNMENT IS OPTIONAL. YOU GET 30 POINTS EXTRA CREDIT IF IT WORKS.

Do Exercise 7.21. This is the same problem as in Assignment #8, except that the solution does not use recursion. The algorithm will have a different running time than Assignment #8 -- for some inputs it will be faster, but for others it will be slower. A sketch of the new algorithm is provided below.

The Routines

Provide a functions Knapsack with the following signature:
int Knapsack( const Vector<int> & A, int K );
Knapsack returns true if there is a subset of A that sums to K and prints out the elements that form the matching subset. Reuse your main from assignment #8; have it prompt for K and the elements of array A, and then make a call to Knapsack and either output the matching sequence or an indication that there is no match.

The Non-Recursive Algorithm

Inside Knapsack declare two local Vectors of size K+1. The first Vector is logically an array of booleans CanBeMatched, initially false. The second is an array of int, PartOfTheMatch. Set CanBeMatched[0] to true. For each value A[i], do the following: check the array of booleans. Set CanBeMatched[j] to be true if it is currently false AND CanBeMatched[j - A[i]] is true. If this is the case, also set PartOfTheMatch[j] to be equal to A[i]. This works out to be a loop (where j runs from K downto A[i]) inside a loop. At the end of the two for loops, CanBeMatched[K] is true if there is a match. The items that form the sum can be found by tracing back through the PartOfTheMatch vector. I'll discuss the algorithm in class.

What to Submit

Place your source code in a single file. The whole program should fit in a page. Submit your source code and run on the data sets below. You may assume that the array will contain at most 30 numbers.

Data Sets

Run on the following data sets.

Recursion Is Slow

Input sequence: 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289, 324, 361, 400, 441, 484, 529, 576, 625, 676, 729, 784, 841, 900.
K: 1 K: 1000 K: 9428 K: 9455
This data set will not terminate in a reasonable amount of time using the recursive algorithm.