Please do this in C++

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; } 

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.

itunes.cpp

// File iTunes.cpp // Implementation for classes // iTunesEntry // iTunesEntryReader // Author: Michael Loceff c 2009

// reads a file containing lines in the format desribed in // iTunes_FormatKey, and provides a vector-like structure // (an iTunesEntryReader object) filled with iTunesEntry objects // for use by the client

#include "iTunes.h"

// iTunesEntryReader methods --------------------------------------------- // looks for a line of the form "#" signifying a // new record to be read and returns true if found bool iTunesEntryReader::isDataLine(string line) { string s; if (line.length() < 1) return false; if (line == "#") return true; return false; }

iTunesEntry &iTunesEntryReader::operator[](int k) { static iTunesEntry dummyReturn; if (k < 0 || k >= numTunes) return dummyReturn; return tunes[k]; }

/* reads 3 lines from the input stream, for example

Eric Clapton Pretending 283

*/

bool iTunesEntryReader::readOneEntry(ifstream &infile, iTunesEntry &tune) { string nextLine, fileTitle, fileArtist, fileTime; int tuneTime;

if ( !infile.eof() ) getline (infile, fileArtist); else return false;

if ( !infile.eof() ) getline (infile, fileTitle); else return false;

if ( !infile.eof() ) getline (infile, fileTime); else return false; // convert string to int istringstream(fileTime) >> tuneTime;

tune.setArtist(fileArtist); tune.setTitle(fileTitle); tune.setTime(tuneTime);

return true; }

// constructor which does entire read operation iTunesEntryReader::iTunesEntryReader(string fileName) { string name; string line; iTunesEntry tune;

numTunes = 0; fileOpenError = false; tuneFile = "NO FILE NAME PROVIDED";

if (fileName.length() == 0) { fileOpenError = true; return; } tuneFile = fileName;

// open file for reading ifstream infile(fileName.c_str()); if (!infile) { fileOpenError = true; return; }

// for each line that starts #. read and add to vector numTunes = 0; while ( !infile.eof() ) { getline (infile, line); if (isDataLine(line)) { if ( !readOneEntry(infile, tune) ) { fileOpenError = true; break; } tunes.push_back(tune); numTunes++; } } infile.close(); }

// iTunesEntry methods --------------------------------------------------- int iTunesEntry::sortKey = iTunesEntry::SORT_BY_ARTIST;

// default constructor iTunesEntry::iTunesEntry() : title(""), artist(""), tuneTime(0) { }

// mutators bool iTunesEntry::setTitle(string sArg) { if (sArg.length() < MIN_STRING || sArg.length() > MAX_STRING) return false; title = sArg; return true; } bool iTunesEntry::setArtist(string sArg) { if (sArg.length() < MIN_STRING || sArg.length() > MAX_STRING) return false; artist = sArg; return true; } bool iTunesEntry::setTime(int nArg) { if (nArg < 0 || nArg > MAX_TIME) return false; tuneTime = nArg; return true; }

int iTunesEntry::convertStringToSeconds(string sToCnvrt) { unsigned int colonPos; int minutes, seconds, lengthOfSecString;

if (sToCnvrt.length() < 1) return 0; colonPos = sToCnvrt.find_first_of(":"); if (colonPos < 0 || colonPos > iTunesEntry::MAX_STRING) return 0;

istringstream(sToCnvrt.substr(0, colonPos)) >> minutes; lengthOfSecString = sToCnvrt.length()-1 - colonPos; istringstream(sToCnvrt.substr(colonPos + 1, lengthOfSecString)) >> seconds;

return minutes*60 + seconds; }

string iTunesEntry::convertTimeToString() const { int minutes, seconds; ostringstream cnvrt1, cnvrt2; string retString = "", strSeconds, strMinutes;

minutes = tuneTime / 60; seconds = tuneTime % 60;

cnvrt1 << minutes; cnvrt2 << seconds;

strMinutes += cnvrt1.str(); strSeconds = cnvrt2.str();

if (strSeconds.length() < 2) strSeconds = "0" + strSeconds;

return strMinutes + ":" + strSeconds; }

bool iTunesEntry::setSortType( int whichType ) { switch (whichType) { case SORT_BY_TITLE: case SORT_BY_ARTIST: case SORT_BY_TIME: sortKey = whichType; return true; default: return false; } return true; }

bool iTunesEntry::operator<(const iTunesEntry &other) const { switch (sortKey) { case SORT_BY_TITLE: return (title < other.title); case SORT_BY_ARTIST: // get last name from string // stack the last name before the first - no worries about trailing last return ( getArtistLastName() + artist < other.getArtistLastName() + other.getArtist() ); case SORT_BY_TIME: return (tuneTime < other.tuneTime); default: return false; } return true; }

bool iTunesEntry::operator>(const iTunesEntry &other) const { return (other < *this); }

bool iTunesEntry::operator==(const iTunesEntry &other) const { return !(other < *this) && !(*this < other); }

bool iTunesEntry::operator!=(const iTunesEntry &other) const { return !(other == *this); }

string iTunesEntry::getArtistLastName() const { // search for first blank from end of string // assume no trailing spaces string retString; int k, length;

length = artist.length(); if ( length < 1 ) return "";

for (k = length-1; k >= 0; k--) { if (artist[k] == ' ') break; }

if (k >= length-1 ) return "";

return artist.substr(k + 1, artist.length()-1 - k); }

itunes.h

// File iTunes.h // Interface for classes // iTunesEntry - Single iTune object from the simplified iTunes data file // iTunesEntryReader - Used to read and return iTunesEntry objects // Author: Michael Loceff c 2009

#ifndef ITUNES_H #define ITUNES_H

#include #include #include #include #include #include using namespace std;

class iTunesEntry { public:

private: string title, artist; int tuneTime;

public: static const unsigned int MIN_STRING = 1; static const unsigned int MAX_STRING = 300; static const int MAX_TIME = 10000000;

iTunesEntry();

//mutators bool setTitle(string sArg); bool setArtist(string sArg); bool setTime(int nArg);

// accessors string getTitle() const { return title; } string getArtist() const { return artist; } int getTime() const { return tuneTime; }

// helpers static int convertStringToSeconds(string sToCnvrt); string convertTimeToString() const;

// comparator tools // could use static const int, instead: private: static int sortKey;

public: static enum { SORT_BY_TITLE, SORT_BY_ARTIST, SORT_BY_TIME } eSortType; static bool setSortType( int whichType ); bool operator<(const iTunesEntry &other) const; bool operator>(const iTunesEntry &other) const; bool operator==(const iTunesEntry &other) const; bool operator!=(const iTunesEntry &other) const; string getArtistLastName() const; };

class iTunesEntryReader { private: vector tunes; int numTunes; bool fileOpenError; string tuneFile; bool readOneEntry(ifstream &infile, iTunesEntry &tune); bool isDataLine(string line);

public: iTunesEntryReader(string fileName); iTunesEntry &operator[](int k); string getFileName() { return tuneFile; } bool readError() { return fileOpenError; } int getNumTunes() { return numTunes; } }; #endif