Write as simple a program as you can manage that will
produce the same results as in the above page for the
subset sum problem. Notice that you've been given code to calculate the
array W. (You are to follow the given algorithm
and the given notation. Many programs that perform similar
calculations are on the Internet.)
First have your program
use the array A = {1,9,5,3,8}.
Use a work array of size 27, that is,
with elements A[0] through A[26].
For this run only, print
the successive steps of the work array W,
so that your output should look exactly like what is on
the Subset Sum page.
Add a function recover(int k) to your code in part (a)
above that will print the actual numbers in the sum
that the algorithm has discovered.
The integer value in W[k] is the last
number in the sum. Say that value is s = W[k].
Then the previous value (next-to-the-last value) of
the sum will be the integer value in W[k-s].
(Notice that W[k-s] = W[k-w[k]], so the notation can look
weird if you don't use a new variable.)
Your function should continue in a loop until you
get to W[0] with value 0. Don't print the 0 as part
of the sum. Test you program with the same values for
A, and print the numbers that sum to 22, that is,
use recover(22).
[ 22 = 9+5+8.]
As a second test, try
it out with the array A = {31,25,17,10,6,5,1}
and the sum 40. (Your work array W will
need to be larger than 27.)
[ 40 = 25+10+5.]
Finally, use A =
{1728,1913,2285,2732,3260,3334,3645,4413,4666,4866,5085,5471,5712,8462,9197,9745};
and the sum 30622. [Of course you need a big
W array here.]
[ Here 30622 is the sum of A[i]
for i in {0,1,4,6,7,9,10,12}, or the sum of the numbers
{1728,1913,3260,3645,4413,4866,5085,5712}. I haven't checked if
this sum can be obtained by adding up a different subset of A.]
Making Change with Coins. We covered this problem in
Making Change.
Now consider making change.
[Note that the Internet is saturated with "smallest number of coins"
programs, and that is one reason I require you to modify
the subset sum program in the way described above.]
Use A = {1,9,5,3,8} and try to duplicate
the results at the above link for a trial run.
There can be more than one way to represent
a sum with the least number of coins.
Use A = {25,21,13,10,7,4,1}, and a sum of 70
to get two different sums with 4 coins:
70 = 25+25+10+10, and 70 = 7+21+21+21.
To get the second sum with the program as I have described
it, you can process the elements of A in the opposite order:
A = {1,4,7,10,13,21,25}. (Or else you can modify
the program to keep overwriting solutions that have
the same number of coins.)
In the same way get two different representations
of 64 as a sum of 4 coins.
[ 64 = 25+13+13+13, and
64 = 1+21+21+21.
Also 64 = 25+25+13+1, though neither run
should get this solution.]
Revision date:2012-10-29.
(Please use ISO
8601, the International Standard.)
