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 indicesarray 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 aniTunesEntry 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 intsremain 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.