{{C++; COMPLEATE MAIN.CPP}}:

Part B (required) - The Subset Sum Problem For iTunesEntries.

Complete the main() and other needed code that solves the subset sum problem for any vector of iTunesEntries.

You have to replace the term int with the term iTunesEntry in most places in the previous lab program, but don't do this mindlessly - some ints remain ints. There is a twist, as well: iTunesEntry does not support the cout << someTuneObject expression which is used in your Sublist class (no doubt, in showSublist()), so you have to overload the << operator as a global scope function to make this happen. Likewise, in your first solution you will have an expression similar (or identical) to this:

 ... choices[j].getSum() + dataSet[k-1] ... 

This works fine if dataSet is a vector of ints, but if it is a vector of iTunesEntries, then it will not work; you can't add an int (the return type of getSum()) to an iTunesObject. Or can you? If you overload the + operator as a global scope function, you can. Therefore, you'll have to make that adjustment. When you make these adjustments, you should be able to use the modified main() and class on iTunesEntry vectors to solve the subset sum problem. Here is your main set up:

int main() { int target = 0; vector dataSet; vector choices; int k, j, numSets, max, masterSum, arraySize, newSum, bestSublist; bool foundPerfect; // read the data iTunesEntryReader tunes_input("itunes_file.txt"); if (tunes_input.readError()) { cout << "couldn't open " << tunes_input.getFileName() << " for input. "; exit(1); } // time the algorithm ------------------------- clock_t startTime, stopTime; startTime = clock(); // create a vector of objects for our own use: array_size = tunes_input.getNumTunes(); for (int k = 0; k < array_size; k++) dataSet.push_back(tunes_input[k]); cin >> target; cout << "Target time: " << target << endl; // code provided by student // // choices[bestSublist].showSublist(); // how we determine the time elapsed ------------------- stopTime = clock(); // report algorithm time cout << " Algorithm Elapsed Time: " << (double)(stopTime - startTime)/(double)CLOCKS_PER_SEC << " seconds." << endl << endl; return 0; } 

Here is an example run. Warning - don't use target times over 1000 until you have debugged the program or you may end up waiting.

Target time: 3600 Sublist ----------------------------- sum: 3600 array[0] = Cowboy Casanova by Carrie Underwood(236) , array[1] = Quitter by Carrie Underwood(220) , array[2] = Russian Roulette by Rihanna(228) , array[ 4] = Monkey Wrench by Foo Fighters(230) , array[5] = Pretending by Eric Clapto n(283) , array[6] = Bad Love by Eric Clapton(308) , array[7] = Everybody's I n The Mood by Howlin' Wolf(178) , array[8] = Well That's All Right by Howlin' Wolf(175) , array[9] = Samson and Delilah by Reverend Gary Davis(216) , arra y[11] = Hot Cha by Roy Buchanan(208) , array[12] = Green Onions by Roy Buchana n(443) , array[13] = I'm Just a Prisoner by Janiva Magness(230) , array[14] = You Were Never Mine by Janiva Magness(276) , array[15] = Hobo Blues by John Lee Hooker(187) , array[16] = I Can't Quit You Baby by John Lee Hooker(182) Algorithm Elapsed Time: 0.67 seconds. 

This time, notice how we get a perfect hour's worth of music in a short list of 79 random tunes. This is typical. If you don't get perfect targets most of the time, your algorithm is probably wrong. Please make sure to implement the algorithm presented in our modules so your code will produce exactly the same sublists as in the Auto Grader's solutions.

Part B run output (test cases) requirement

Required Targets: 0, 1200, 3600, 4799, 100000

Other Targets will be checked by the Auto Grader.

MAIN.CPP:

#include #include #include #include "iTunes.h" #include using namespace std;

// global scope function prototypes ---------------- int operator+(int n, const iTunesEntry & tune); ostream & operator<<(ostream & out, const iTunesEntry & tune);

// global scope helper double computeMasterSum( vector data ); void showEntireVector( vector data );

// --------------- Sublist Prototype --------------- class Sublist { // code provided by student // // public: Sublist addItem( int indexOfItemToAdd ); void showSublist() const; // code provided by student // // };

// ------------------ main ------------------

int main() { int target = 0; vector dataSet; vector choices; int k, j, numSets, max, masterSum, arraySize, newSum, bestSublist; bool foundPerfect, needAlgorithm;

// read the data iTunesEntryReader tunesInput( "itunes_file.txt" ); if ( tunesInput.readError() ) { cout << "couldn't open " << tunesInput.getFileName() << " for input. "; exit( 1 ); }

// time the algorithm ------------------------- clock_t startTime, stopTime; startTime = clock();

// create a vector of objects for our own use: arraySize = tunesInput.getNumTunes(); for ( int k = 0; k < arraySize; k++ ) dataSet.push_back( tunesInput[k] );

cin >> target; cout << "Target time: " << target << endl;

// dispose of easy case immediately to save lots of time masterSum = (int) computeMasterSum( dataSet ); if ( target >= masterSum ) { cout << "Solution is entire master set with sum = " << masterSum << endl; showEntireVector( dataSet ); needAlgorithm = false; } else needAlgorithm = true;

if ( needAlgorithm ) { // code provided by student // //

choices[bestSublist].showSublist();

// determine the time elapsed ------------------- stopTime = clock(); cout << " Algorithm Elapsed Time: " << (double)(stopTime - startTime) / (double)CLOCKS_PER_SEC << " seconds." << endl << endl;

return 0; } }

// global scope functions --------------------------- int operator+(int n, const iTunesEntry & tune) { // code provided by student // // }

ostream & operator<<(ostream & out, const iTunesEntry & tune) { // code provided by student // // }

// Helper method to compute full sum double computeMasterSum( vector data ) { // code provided by student // // }

void showEntireVector( vector data ) { // code provided by student // // }

// --------------- Sublist Method Definitions ---------------

void Sublist::showSublist() const { int k;

cout << "Sublist ----------------------------- " << endl; cout << " sum: " << sum << endl; for ( k = 0; k < (int)indices.size(); k++ ) cout << " array[" << indices[k] << "] = " << (*originalObjects)[indices[k]] << ((k == (int)indices.size() - 1) ? " " : ", "); }

Sublist Sublist::addItem( int indexOfItemToAdd ) { // code provided by student // //

}