See file
Assignment 1 - The Subset-Sum Problem
Parts A and B are required. Part C is optional and is worth two points extra credit (but must be submitted in addition to, and along with, Part A). Make sure you have read and understood
both modules A and B this week, and
module 2R - Lab Homework Requirements
before submitting this assignment. Hand in only one program, please.
Part A (required) - The Subset Sum Problem For Ints
Using java.util.ArrayLists, create a simple main() that solves the subset sum problem for any ArrayList of ints. Here is an example of the set-up and output. You would fill in the actual code that makes it happen.
import java.util.*;
//------------------------------------------------------
public class Foothill
{
// ------- main --------------
public static void main(String[] args) throws Exception
{
int target = 72;
ArrayList<Integer> dataSet = new ArrayList<Integer>();
ArrayList<Sublist> choices = new ArrayList<Sublist>();
int k, j, numSets, max, kBest, masterSum;
boolean foundPerfect;
dataSet.add(2); dataSet.add(12); dataSet.add(22);
dataSet.add(5); dataSet.add(15); dataSet.add(25);
dataSet.add(9); dataSet.add(19); dataSet.add(29);
// code supplied by student
choices.get(kBest).showSublist();
}
}
The local variables you see above are not required; they come from my solution. If you want to use different local variables, feel free.
Your output style can be different from mine, as long as it is contains equivalent information and is easy to understand. However, show enough runs to prove your algorithm works, and show at least one run that does not meet target, exactly. Also, provide a special test to quickly dispose of the case in which the target is larger than the sum of all elements in the master set. This way, any target that is too large will not have to sit through a long and painful algorithm. Demonstrate that this works by providing at least one run that seeks a target larger than the sum of all master set elements.
Finally, you are not finding all sub-lists, just one representative solution. There may be other sub-lists that do the job, but our algorithm only finds the first one it detects. (If you want to show all the solutions, that's fine.)
A run would look like this:
Target time: 72
Sublist -----------------------------
sum: 72
array[0] = 2,
array[2] = 22,
array[3] = 5,
array[4] = 15,
array[6] = 9,
array[7] = 19
Notice how the target is precisely met. This is not unusual when you have a varied data set. However, for the above data, if you ran a target of 13, it would not be met precisely, and this is also a good test of your algorithm. Test it well, not just on one or two values.
class Sublist
I have prompted you with all the essential details of the class Sublist that will support your algorithm. I'll add a couple more hints:
To create an empty Sublist (which is the first thing you need to do in order to prime the pump) just instantiate one Sublist object. By definition, it represents an empty set, since it will have no elements in its internal indices array list.
The addItem() member function is clearly the most interesting of the outstanding instance methods. In that method you will have to create a new Sublist object whose sum is the sum of the calling object plus the value of the new item added. This will require a slightly different syntax for an int data set than it will for an iTunesEntry data set. In the latter case, you'll need to get specific inside addItem() about what value within iTunesEntry you are adding. This means addItem() is going to have syntax that ties it firmly to the underlying data set. That's okay for this part and the next, but not for option C.
Part B (required) - The Subset Sum Problem For iTunesEntries
Next create a main() that solves the subset sum problem for any ArrayList of iTunesEntries. You have to replace the term int with the term iTunesEntry in most places in the above program, but don't do this mindlessly - some ints remain ints. There is a twist, as well: In your first solution you will have an expression similar (or identical) to this:
... choices.get(j).getSum() + dataSet.get(k) ...
This works fine if dataSet is a list of ints, but if it is a list of iTunesEntries, then it will not work; you can't add an int (the return type of getSum()) to an iTunesObject. So you need to extract the appropriate number from the iTunesEntry object on the right. Here is your main set up and run:
import cs_1c.*;
import java.text.*;
import java.util.*;
//------------------------------------------------------
public class Foothill
{
// ------- main --------------
public static void main(String[] args) throws Exception
{
int target = 3600;
ArrayList<iTunesEntry> dataSet = new ArrayList<iTunesEntry>();
ArrayList<Sublist> choices = new ArrayList<Sublist>();
int k, j, numSets, max, kBest, arraySize, masterSum;
boolean foundPerfect;
// for formatting and timing
NumberFormat tidy = NumberFormat.getInstance(Locale.US);
tidy.setMaximumFractionDigits(4);
long startTime, stopTime;
// read the iTunes Data
iTunesEntryReader tunesInput = new iTunesEntryReader("itunes_file.txt");
// test the success of the read:
if (tunesInput.readError())
{
System.out.println("couldn't open " + tunesInput.getFileName()
+ " for input.");
return;
}
// load the dataSet ArrayList with the iTunes:
arraySize = tunesInput.getNumTunes();
for (k = 0; k < arraySize; k++)
dataSet.add(tunesInput.getTune(k));
choices.clear();
System.out.println("Target time: " + target);
// code supplied by student
choices.get(kBest).showSublist();
}
}
Here is a run. Warning - don't use target times over 1000 until you have debugged the program or you may run out of memory.
Target time: 3600
Sublist -----------------------------
sum: 3600
array[0] = Carrie Underwood | Cowboy Casanova | 3:56,
array[1] = Carrie Underwood | Quitter | 3:40,
array[2] = Rihanna | Russian Roulette | 3:48,
array[4] = Foo Fighters | Monkey Wrench | 3:50,
array[5] = Eric Clapton | Pretending | 4:43,
array[6] = Eric Clapton | Bad Love | 5:08,
array[7] = Howlin' Wolf | Everybody's In The Mood | 2:58,
array[8] = Howlin' Wolf | Well That's All Right | 2:55,
array[9] = Reverend Gary Davis | Samson and Delilah | 3:36,
array[11] = Roy Buchanan | Hot Cha | 3:28,
array[12] = Roy Buchanan | Green Onions | 7:23,
array[13] = Janiva Magness | I'm Just a Prisoner | 3:50,
array[14] = Janiva Magness | You Were Never Mine | 4:36,
array[15] = John Lee Hooker | Hobo Blues | 3:07,
array[16] = John Lee Hooker | I Can't Quit You Baby | 3:02
Algorithm Elapsed Time: 0.149 seconds.
Run requirements stated in Part A are still required, here.
Again, notice how we get a perfect hour's worth of music in a short list of 72 random tunes. Again, this is typical. If you don't get perfect targets most of the time, your algorithm is probably wrong.
Part C (optional) - "Genericizing" Class Sublist [2 POINTS EXTRA CREDIT]
After having extended the solution from ints to iTunesEntry, you can genericize the Sublist class, but it will require some adjustments. Most notably, since the addItem() method referred to a specific iTunesEntry accessor method in part B, you cannot keep them there. One way to overcome this is to change the signature of addItem() so that it takes a second parameter, namely, an int representing the value (i.e., playing time in the case of the iTunesEntry) of the new item you want to add to the Sublist.
Do this, and repeat the iTunesEntry solution, this time supplying iTunesEntry as a type parameter to the Sublist class template. Here are the first few lines of main():
//------------------------------------------------------
public class Foothill
{
// ------- main --------------
public static void main(String[] args) throws Exception
{
int target = 4300;
ArrayList<iTunesEntry> dataSet = new ArrayList<iTunesEntry>();
ArrayList<Sublist<iTunesEntry>> choices
= new ArrayList<Sublist<iTunesEntry>>();
int k, j, numSets, max, k_best, array_size;
boolean found_perfect;
// etc.
The runs should be the same. YOU MUST SUBMIT PARTS A AND B ALSO, IF YOU DO THIS OPTION. Also, you must show that your template class code works on both ints and iTunes to get credit for this part.
Run requirements stated in Part A are still required, here.
Another Option
You can create a generic to encapsulate the algorithm. This requires some design thought and decision making. It is tricky so I don't recommend it unless you have finished the above very early (and I do not have an instructor solution for this, currently). Of course, all run requirements above are still in force.
Once your assignment is graded and returned, you can view the instructor solution here:
Quiz List
Your access code will be provided in your graded assignment comments. Find the assignment in the list, click "Take Survey" and you will see the solution. Even though it is called a "Quiz", it is actually just a solution; there is no need to submit anything, just open the quiz and see the solution.