# the subset sum problem 1

#### 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.

#### 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.

## Leave a Reply

Want to join the discussion?Feel free to contribute!