Assignment 1 Spring 2006
Use Dynamic Programming to solve the Knapsack problem
for reasonably limited inputs.
Here is what I would expect a sample run of your program
to look like:
$ knapsack
How many elements in the set? 9
Enter them: 15 5 11 18 11 14 4 8 14
What is the desired sum? 21
A sum of 21 can not be made.
Nearest attainable sum = 20.
The subset is 5 11 4.
$ knapsack
How many elements in the set? 9
Enter them: 15 5 11 18 11 14 4 8 14
What is the desired sum? 68
The subset is 15 5 11 18 11 8.
As you can see, you are not expected to print the table,
it is simply an intermediate data structure that your
program will create, use, then discard.
You do not need to duplicate these sample sessions,
but make your user interface reasonably friendly, or
at least usable.