Я чувствую себя действительно глупо, приходя задавать этот вопрос здесь сегодня, после того, как все задавали вопросы о понимании алгоритма. Но я больше не смотрю на эту вещь прямо. В любом случае, это ранняя проблема, решаемая с помощью запоминания и динамического программирования. Проблема в том, что распечатка моих ответов не соответствует требованиям.
Все, что я хочу, это второй взгляд на это, и если кто-то может указать мне, где я ошибаюсь.
Ценю за помощь.
Это файл ProfitHeader.h
#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 to make sure that key elements Match. will 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 is the iff conditional
else if(this->programmingWork < rhs.programmingWork)
return true;
else
return false;
}
};
//Global Operator-. This will 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 is the Project Struct. It should contain the resources and data from the file.
struct Project{
string name;
Resources resources;
Money profit;
Project(string n, Resources re, Money p) : name(n), resources(re), profit(p) {}
};
//Definition of the ValueMap
typedef map<pair<Resources, vector<Project>::size_type>, pair<Money, bool>> ValueMap;
}
#endif
Это мой main.cpp
#include <iostream>
#include <fstream>
#include <sstream>
#include <exception>
#include "ProfitHeader.h"
using namespace std;
using namespace kproblem;
//The following was provided to us on the 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 from " + fileName);
}
//Class Best Profit.
//This class will calculate the best possible profit we can get.
Money bestProfit(const vector<Project> & projects, Resources res, ValueMap & valMap,int n){
//initialize the best 2 possible solutions.
Money best1;
Money best2;
Money map; // the map where ou answers are stored
// First check if we are not at the end of the projects
if(n == 0){
return 0;
}
//now we are going to check the best project possible.
//Check the subinstance if it was 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 the subinstance is solved. if it is return the value.
best1 = bestProfit(projects, res, valMap, n-1);//first best possible solution
//check the resources for the last project only. Fopr the 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 the above are requiered as it is necessary to check for all of them when doing the calculations.
best2 = bestProfit(projects, res - projects[n-1].resources, valMap, n-1) + projects[n-1].profit;
}
else{
best2 = 0;
}
//after the whole check compare the results and store the best possible result in the 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. This will call Best profit and help us print the final results.
void reportBestProfit(vector<Project> projects, Resources resources){
ValueMap valueMap;
//Variables for the total resources used.
Money liq = 0;
Money ow = 0;
Money pw = 0;
int n = 1000; //number of projects, put here for fast testing
Money bestP = bestProfit(projects, resources, valueMap, n);
//Iterate the valuemap and print the best projects available to us.
cout << "Selected Projects -" << endl;
for(int i= 1; i <= 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 the resources consumed.
for(int i= 1; i <= 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 the 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 be changed for 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;
}
Файл проекта, содержащий проекты, можно временно загрузить здесь:
https://rapidshare.com/files/459861869/Proj5Data.txt
Полагаю, проблема в поиске valmap, но я перепробовал все виды комбинаций, и он вообще не работает.
Наконец, это последняя распечатка, которую я должен получить из этого:
Но вместо этого я получаю все остальные результаты, включая некоторые из тех, которые мне нужны: 
Еще раз спасибо за того, кто может ударить меня по голове и сказать, что вы, FOO, вы не должны больше этим заниматься :).