Prog 5
Prog 5
Prog 5
edu/classes/cs345/fall07/
As V [5, 13] = 13, it is possible to nd a subset of S that sums to C. As this is a small problem size, we can easily nd the subset by inspection: {2, 5, 6}. As mentioned above, youll need to employ the tables content to nd a more ecient algorithmic way to nd the subset.
Data: Your program is to accept the name of a data le from the command line. The format of a data le is straightforward. The le contains one integer per line. The rst line provides C. Lines 2 through n + 1 contain the elements of S, in no particular order. As S is intended to be a set, your program will need to check it for duplicates. If any are found, the program is to terminate with a meaningful error message. Remember that the empty set is a set. We wont be supplying any sample data les for this assignment, as we expect you can create them on your own with little trouble. Output: The initial output of your program is to be the value of C and the content of S: Subset Sum Problem: C = 13; S = {1,2,5,6,9}.
Each of your two solutions (dynamic programming and exhaustive search) is to display one of two messages. If a solution is found, display: SUCCESS was achieved using Dynamic Programming in # minutes and ##.## seconds! The sum of {2, 5, 6} equals 13. Of course, the algorithm name and execution time will vary, and you are to use as many digits as is necessary to display the quantity of minutes. When a solution cannot be found, display: FAILURE was suffered by Dynamic Programming after # minutes and ##.## seconds. No subset of S sums to 13. Separate the three output sections from one another single blank lines. Very important: Construct your program to compute and display the dynamic programming solution before it computes and displays the exhaustive search solution! This will allow the TAs to verify the correctness of your dynamic programming solution on large problems without having to wait for the exhaustive search. Hand In: On the due date, turn in a printed listing of your welldocumented program statements. As usual, you are required to submit your completed program le(s) to the class submission directory, using the turnin command. The turnin location for this assignment is cs345p5. Name your main program source le Prog5.java so that we dont have to guess which le to compile/translate. Other Requirements, Hints, and Miscellaneous Babbling: The knapsack problem is a member of the NPComplete class of problems, which means that it has no known ecient solution. Well talk a little bit about such problems later in the course. As usual, we plan to test your code with a variety of data les. Thus, so should you. The diculty level of this assignment does not reach that of previous programs. This is intentional, given the holiday between now and the due date, and the time of the semester. Even so, an early start is recommended. This is the last program of the semester. Savor it, cherish it, for soon it will be but a misty memory . . .