01背包问题【动态规划】

#ifndef ___1package__package__
#define ___1package__package__

#include <iostream>
#include <string>
#include <vector>
using namespace std;

class Package{
public:
    void init(string dataSource);
    void print();
private:
    void compute();
    int m_nN;  // The number of object
    int m_nW;  // The max weight of package
    vector<int> m_vecWeight;  // The weight of object
    vector<int> m_vecValue;   // The value of object
    vector<vector<int> > m_vecMatrix;  // The results matrix
    
};

#endif /* defined(___1package__package__) */

//
//  package.cpp
//  01package

#include "package.h"
#include <fstream>

void Package::init(string dataSource){
    // read data from datasource
    ifstream file;
    file.open(dataSource);
    if (file.is_open()){
        string buffer;
        file>>m_nW;
        file>>m_nN;
        m_vecWeight.clear();
        m_vecWeight.push_back(0);
        m_vecValue.clear();
        m_vecValue.push_back(0);
        int w, v;
        for (int i=0; i<m_nN; ++i) {
            file>>w>>v;
            m_vecWeight.push_back(w);
            m_vecValue.push_back(v);
        }
        while(!file.eof()){
            file>>buffer;
            cout<<buffer<<endl;
        }
    }
    file.close();
    
    m_vecMatrix.clear();
    // set first row and first column to zero
    for (int i=0; i<=m_nN; ++i) {
        m_vecMatrix.push_back(vector<int>(m_nW+1, 0));
    }
    
}

void Package::print(){
    compute();
    cout<<"\n=====The Results======\n"<<"The max value: "<<m_vecMatrix[m_nN][m_nW]<<endl;
}

void Package::compute(){
    for (int i=1; i<=m_nN; ++i) {
        for (int j=1; j<=m_nW; ++j) {
            int cur_weight = m_vecWeight[i];
            if (cur_weight>j) {
                m_vecMatrix[i][j] = m_vecMatrix[i-1][j];
            } else{
                m_vecMatrix[i][j] = max<int>(m_vecMatrix[i-1][j-cur_weight]+m_vecValue[i], m_vecMatrix[i-1][j]);
            }
        }
    }
}