Assignment #8, COP-3337
Do Exercise 7.22.
A sketch of an algorithm is provided below.
The Routines
Provide two functions Knapsack with the following signatures:
int Knapsack( const Vector<int> & A, int K );
int Knapsack( const Vector<int> & A, int K, int Low, int High );
The first version returns true if there is a subset of A
that sums to K.
The second version returns true if there is a subset of A,
using only items in the subarray A[Low...High],
that sums to K.
Both versions print out the elements that form the matching subset.
It should be a simple matter to implement the first version
of Knapsack by making a call to the second version.
The second version is the recursive algorithm that will be described below.
Provide a main that will 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 Recursive Algorithm
Recall that the function prototype is
int Knapsack( const Vector<int> & A, int K, int Low, int High );
Here are the basic cases:
Base Case
If Low>High, then there is no element in the subarray,
and Knapsack should return true only if
K==0.
Recursive Case
Otherwise there is one or more element. In that case, there is
a matching sequence if either of the following cases is true:
- Knapsack( A, K, Low+1, High ) is true
- Knapsack( A, K - A[ Low ], Low+1, High ) is true
The first case says that there is a match using elements
in positions Low+1 to High
The second case says that there is a match using element
A[Low] plus other elements in positions
Low+1 to High.
In the second case, A[Low] is one of the elements
that will be part of the match and can be printed.
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
The first two sets are guaranteed to have matches for any value of
K (that is not too large). The third set is not.
Powers of 2
Input sequence: 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096,
8192, 16384, 32768, 65536.
K: 100000
Fibonacci Numbers
Input sequence: 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610,
987, 1597, 2584, 4181, 6765, 10946.
K: 12000
Nothing Special
Input sequence: 2134, 5436, 8796, 6578, 1234, 9999, 4534, 1492, 1996, 1997,
3859, 3337, 3530, 1999, 6405.
K: 11000;
K: 12000;
K: 13000;
K: 14000;