финальный проект, динамическое программирование. Нужен второй набор глаз - PullRequest
0 голосов
/ 30 апреля 2011

Я чувствую себя действительно глупо, приходя задавать этот вопрос здесь сегодня, после того, как все задавали вопросы о понимании алгоритма. Но я больше не смотрю на эту вещь прямо. В любом случае, это ранняя проблема, решаемая с помощью запоминания и динамического программирования. Проблема в том, что распечатка моих ответов не соответствует требованиям. Все, что я хочу, это второй взгляд на это, и если кто-то может указать мне, где я ошибаюсь. Ценю за помощь. Это файл 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, но я перепробовал все виды комбинаций, и он вообще не работает.

Наконец, это последняя распечатка, которую я должен получить из этого: result

Но вместо этого я получаю все остальные результаты, включая некоторые из тех, которые мне нужны: result2

Еще раз спасибо за того, кто может ударить меня по голове и сказать, что вы, FOO, вы не должны больше этим заниматься :).

Ответы [ 2 ]

0 голосов
/ 30 апреля 2011

ОК, так что да, у меня есть ответ.Завершено (после редактирования)

void reportBestProfit(vector<Project> projects, Resources resources){
    ValueMap valueMap;
    //Variables for the total resources used.
    Money liq = 0;
    Money ow = 0;
    Money pw = 0;
    vector<Project> result;
    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;
    // this loop just iterates through the values, it does not check the initial resources.
    for(int i= 999; i > 0; i--){
        //if(valueMap.find(make_pair(resources, i-1)) == valueMap.end()){
        //check first If I still have resources available
        if(resources.liquidity >=0 && resources.officeWork >= 0 && resources.programmingWork >= 0){
            if(valueMap.find(make_pair(resources, i))->second.second == true){
                //when I find the first true, I need to substract the resources of it from the base resources, 
                //to ask the question again.
                resources.liquidity -= projects.at(i-1).resources.liquidity;
                resources.officeWork -= projects.at(i-1).resources.officeWork;
                resources.programmingWork -= projects.at(i-1).resources.programmingWork;
                //Push the results into a vector for the printout
                result.push_back(Project(projects.at(i-1).name, 
                             Resources(projects.at(i-1).resources.liquidity,
                                       projects.at(i-1).resources.officeWork, 
                                       projects.at(i-1).resources.programmingWork),
                                     projects.at(i-1).profit));
                //Also in one shot add together the resources used
                liq +=  projects.at(i-1).resources.liquidity;
                ow += projects.at(i-1).resources.officeWork;
                pw += projects.at(i-1).resources.programmingWork;
            }
        }
    }
    //Print the saved vector in reverse order
    for(int size = result.size(); size != 0; size--){
        cout << "    " << result.at(size -1).name;
        cout << " " << result.at(size -1).resources.liquidity;
        cout << " " << result.at(size -1).resources.officeWork;
        cout << " " << result.at(size -1).resources.programmingWork;
        cout << " " << result.at(size -1).profit << endl;
    }   
    cout << "Total Resources Used -" << endl;
    ////Print the resources consumed.
    cout << "    " << "Liquidity: " << liq <<endl;
    cout << "    " << "Office Work: " << ow <<endl;
    cout << "    " << "Programming Work: " << pw <<endl;
    //Print the total Profit.
    cout << "Profit: " << bestP << endl;
    system("PAUSE");
}

По сути, я не вычитал ресурсы, поэтому у меня всегда было перерасход ресурсов, но однажды я сделал этот альт!оно работает.Спасибо, ребята, что посмотрели на это, наверное, мне просто нужно было вдохновение сегодня утром.

0 голосов
/ 30 апреля 2011

удаление этого избавит от начальных чисел во второй части вывода

        cout << valueMap.find(make_pair(resources, i))->second.first; //money
        cout <<" "<< valueMap.find(make_pair(resources, i))->second.second; //boolean
        cout << "    "

значения, которые вы печатаете в этот момент, не были отфильтрованы и упорядочены, поэтому я думаю, что вашпечать этих значений

, но у вас нет кода для печати "The total resources used -" part

...