最终项目，动态规划。需要第二双眼睛

Question

在昨天困扰大家理解算法之后，我觉得今天在这里问这个问题真的很愚蠢。但我不再直视这件事了。无论如何，这是一个背包问题，通过记忆和动态编程来解决。问题是我的答案的打印输出与要求不符。 我想要的只是再看一遍，是否有人能指出我哪里错了。 感谢所有的帮助。 这是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 find 上，但我尝试了各种组合，但根本不起作用。

最后，这是我应该从中得到的最终打印输出：

但是我得到了所有其他结果，包括我需要的一些结果：

再次感谢你能打我的头并说，你这个FOO，你不应该再这样做了:)。

Answer 1

删除它会去掉输出第二部分的前导数字

        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 -"

部分

Answer 2

好吧，是的，我确实有答案了。现已完成（编辑后）

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

基本上我没有减去资源，所以我总是有多余的资源，但是一旦我做了那个中提琴！有用。谢谢你们看到它，我想我今天早上只是需要灵感。