i feel stupid coming ask question here today after bugging yesteday on understanding algorithm. not looking @ thing straight anymore. anyways, knapsack probled, solved memoization , dynamic progrmming. problem printout of answers not matching requierements. want second @ , if can point me wrong at. appreciated help. profitheader.h file
#ifndef profitheader_h_ #define profitheader_h_ #include <string> #include <map> #include <vector> using namespace std; namespace kproblem{ typedef int money; typedef int labor; struct resources{ money liquidity; labor officework; labor programmingwork; resources(money li, labor of, labor pro) : liquidity(li), officework(of), programmingwork(pro){} //operator -= resources & operator -=( const resources &rhs ){ liquidity -=rhs.liquidity; officework -=rhs.officework; programmingwork -=rhs.programmingwork; return *this; } //operator< used make sure key elements match. not modify (this) bool operator<(const resources & rhs) const{ if(this->liquidity < rhs.liquidity) return true; else if(this->liquidity > rhs.liquidity) return false; else if(this->officework < rhs.officework) return true; else if(this->officework > rhs.officework) return false; //this iff conditional else if(this->programmingwork < rhs.programmingwork) return true; else return false; } }; //global operator-. not modify (this). resources operator-( const resources & lhs, const resources & rhs ){ return resources(lhs.liquidity - rhs.liquidity, lhs.officework - rhs.officework, lhs.programmingwork - rhs.programmingwork); } //this project struct. should contain resources , data file. struct project{ string name; resources resources; money profit; project(string n, resources re, money p) : name(n), resources(re), profit(p) {} }; //definition of valuemap typedef map<pair<resources, vector<project>::size_type>, pair<money, bool>> valuemap; } #endif this main.cpp
#include <iostream> #include <fstream> #include <sstream> #include <exception> #include "profitheader.h" using namespace std; using namespace kproblem; //the following provided on program class io_exception : public runtime_error { public: io_exception(const string & message) : runtime_error(message) { } }; void readprojects(vector<project> & projects, const string & filename) { ifstream infile(filename.c_str()); if (!infile) throw io_exception("could not open " + filename); string oneline; unsigned int linenum = 0; while (getline(infile, oneline)) { istringstream st(oneline); linenum++; string name; money liquidity; labor officework; labor programmingwork; money profit; st >> name; st >> liquidity; st >> officework; st >> programmingwork; st >> profit; if (st.fail()) { cerr << "skipping line number " << linenum << ": " << oneline << endl; continue; } string junk; if (st >> junk) { cerr << "skipping line number " << linenum << ": " << oneline << endl; continue; } projects.push_back(project(name, resources(liquidity, officework, programmingwork), profit)); } if (!infile.eof()) throw io_exception("error reading " + filename); } //class best profit. //this class calculate best possible profit can get. money bestprofit(const vector<project> & projects, resources res, valuemap & valmap,int n){ //initialize best 2 possible solutions. money best1; money best2; money map; // map ou answers stored // first check if not @ end of projects if(n == 0){ return 0; } //now going check best project possible. //check subinstance if solved. if(valmap.find(make_pair(res, n-1)) != valmap.end()){ map = valmap.find(make_pair(res, n-1))->second.first; return map; }//check if subinstance solved. if return value. best1 = bestprofit(projects, res, valmap, n-1);//first best possible solution //check resources last project only. fopr second best possible solution. if(res.liquidity >= projects.at(n-1).resources.liquidity && res.officework >= projects.at(n-1).resources.officework && res.programmingwork >= projects.at(n-1).resources.programmingwork){// feasability check. //all above requiered necessary check of them when doing calculations. best2 = bestprofit(projects, res - projects[n-1].resources, valmap, n-1) + projects[n-1].profit; } else{ best2 = 0; } //after whole check compare results , store best possible result in map. if(best1 >= best2){ valmap.insert(make_pair(make_pair(res, n), make_pair(best1,false))); return best1; } else{ valmap.insert(make_pair(make_pair(res, n), make_pair(best2,true))); return best2; } } //reportbestprofit. call best profit , print final results. void reportbestprofit(vector<project> projects, resources resources){ valuemap valuemap; //variables total resources used. money liq = 0; money ow = 0; money pw = 0; int n = 1000; //number of projects, put here fast testing money bestp = bestprofit(projects, resources, valuemap, n); //iterate valuemap , print best projects available us. cout << "selected projects -" << endl; for(int i= 1; <= 1000; i++){ //if(valuemap.find(make_pair(resources, i-1)) == valuemap.end()){ if(valuemap.find(make_pair(resources, i))->second.second == true){ //if(valuemap.find(make_pair(resources, i))->second.first != valuemap.find(make_pair(resources, i-1))->second.first){ //cout << valuemap.find(make_pair(resources, i))->second.first; //money //cout <<" "<< valuemap.find(make_pair(resources, i))->second.second; //boolean cout << " " << projects.at(i-1).name << " " << projects.at(i-1).resources.liquidity <<" ";//projects cout << projects.at(i-1).resources.officework << " " << projects.at(i-1).resources.programmingwork; cout << " " << projects.at(i-1).profit << endl;//profit //} } } cout << "total resources used -" << endl; //print resources consumed. for(int i= 1; <= 1000; i++){ if(valuemap.find(make_pair(resources, i))->second.second == true){ liq += projects.at(i-1).resources.liquidity; ow += projects.at(i-1).resources.officework; pw += projects.at(i-1).resources.programmingwork; } } cout << " " << "liquidity: " << liq <<endl; cout << " " << "office work: " << ow <<endl; cout << " " << "programming work: " << pw <<endl; //print total profit. cout << "profit: " << bestp << endl; system("pause"); } int main() { vector<project> projects; try { readprojects(projects, "proj5data.txt"); } catch (const io_exception & ex) { cerr << "io error from: " << ex.what() << endl; return 1; } //these values can changed different analysis on projects. money liquidity = 200; labor officework = 450; labor programmingwork = 1000; cout << "available resources - " << endl << " liquidity: " << liquidity << endl << " office work: " << officework << endl << " programming work: " << programmingwork << endl; reportbestprofit(projects, resources(liquidity, officework, programmingwork)); return 0; } the project file contains projects can downloaded temporarily here:
https://rapidshare.com/files/459861869/proj5data.txt my guess problem on valmap find, have tried kinds of combinations , not work @ all.
finally final printout should getting this: 
but instead getting these other results, including of ones need:
again thank 1 can slap me in head , say, foo, shouldn't doing anymore :).
removing rid of leading numbers on second part of output
cout << valuemap.find(make_pair(resources, i))->second.first; //money cout <<" "<< valuemap.find(make_pair(resources, i))->second.second; //boolean cout << " " the values print @ point haven't been filtered , ordered why think printing these values
but don't have code print "the total resources used -" part
Comments
Post a Comment