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.