Algorithms: Backpack problem, Greedy , Dynamic Programming techniques (C++)

This example shows an OO approach to the backpack (rumsack) problem, it implements different techniques (greedy, dynamic programming), it also generates random items and backpack's capacity.

backpack.h

#ifndef BACKPACK_H_INCLUDED
#define BACKPACK_H_INCLUDED

#include
#include 
#include 
#include 
using namespace std;
//A backpack Item
class Item {
public:
    Item(double w, double b):_weight(w),_benefit(b){
    if(_weight==0) throw -100;
    }
    virtual ~Item() {}
    void setWeight(double w) { _weight = w; }
    void setBenefit(double b) { _benefit = b;}
    double getRatio(){ return _benefit/_weight; }

    double _weight;
    double _benefit;
    double _ratio;

};

class Backpack {
public:
    Backpack(double mw) {
        _maxWeight = mw;
        _items = new vector;
        _totBenefit = 0;
        _currentWeight = 0;
    }
   virtual ~Backpack() {}
    virtual void computeAddItems(vector &items) {
    //In this case we use raw algorithm
        double delta;
        vector::iterator it;
        for(it=items.begin();it!=items.end();it++){
           Item * i = *it;
            delta = _maxWeight - (_currentWeight + i->_weight);
            if(delta <=0)
                break;
            _currentWeight = _currentWeight + i->_weight;
            _totBenefit = _totBenefit + i->_benefit;
            _items->push_back(i);
        }


    }


    vector * getItems() { return _items; }

    virtual void displayResults();
    virtual double getTotalBenefit();


    double _maxWeight = -1;
    double _currentWeight=0;
    double _totBenefit=0;
    vector * _items;
    vector * _sol;

};

void Backpack::displayResults(){

cout<< "Items added to Backpack" << endl;
vector::iterator it;
int i = 1;
for(it=_items->begin();it!= _items->end();it++){
    Item * item = *it;
    cout << "Item n:" << i << " Weight:" << item->_weight << " Benefit:" << item->_benefit << " Ratio: " << item->getRatio() << endl;
    i++;
}

cout << " Total sum of benefit : " << this->getTotalBenefit() << endl;
}

double Backpack::getTotalBenefit(){

    _totBenefit = 0;
    for(int i=0;i<_items->size();i++)
        _totBenefit = _totBenefit + _items->at(i)->_benefit;



return _totBenefit;

}

class BackpackGreedy: public Backpack {
public:
    BackpackGreedy(double mw):Backpack(mw){}
    virtual ~BackpackGreedy() {}
    virtual void computeAddItems(vector & items);

    vector sortItems(vector& items);



};

vector BackpackGreedy::sortItems(vector & items){

for(int i=0;i<(items.size() -1);i++){

Item* i1 = items.at(i);

     for(int j=(i+1);j_ratio>i1->_ratio){
           std::swap(items.at(i),items.at(j));

        }

    }

}

return items;


}

void BackpackGreedy::computeAddItems(vector & items) {

    vector  sortedItems = sortItems(items);

    Backpack::computeAddItems(sortedItems);

}

class BackpackDynamic: public Backpack {
public:
    BackpackDynamic(double mw):Backpack(mw) {}
    virtual void computeAddItems(vector& items);



};

void BackpackDynamic::computeAddItems(vector &items){
this->_sol = new vector(items.size());
for(int i=0;i_sol->at(i) = (this->_currentWeight + items.at(i)->_weight<=this->_maxWeight)? true : false;
    if(_sol->at(i)){
        this->_currentWeight = this->_currentWeight + items.at(i)->_weight;
        this->_items->push_back(items.at(i));
    }

}


}




class BackpackRunner {
public:

    virtual int run();

protected:

    vector generateItems(int num);
    double sum;
    double generateBackpackCapacity(int max);


};

vector BackpackRunner::generateItems(int n) {
Item * item = nullptr;
double w,b;
vector items;
  if(n>100){
    cout<< "Generating Max items = 100" << endl;
    n = 100;
    }
    else
        cout << "Generating " << n << " items " << endl;
int i = 0;
while(i items = generateItems(10);
double capacity = generateBackpackCapacity(50);
cout << " Items number: " << items.size() << endl;
cout << " Backpack capacity : " << capacity << endl;
try
{


for(int i=0;i<3;i++){
if(i==0){
bp1  = new Backpack(capacity);
}else if(i==1){
    mesg = "Backpack Greedy Technique";
    bp1  = new BackpackGreedy(capacity);
}else{
    mesg = "Backpack Dynamic Programming Technique";
    bp1  = new BackpackDynamic(capacity);
}
cout << "---------" << mesg << "---------"<computeAddItems(items);

bp1->displayResults();
cout << "-------------------------------" << endl;

}

}catch(exception e){
    cout << " BackpackRunner an exception occurred : " << e.what() << endl;
}

return 0;
}




#endif // BACKPACK_H_INCLUDED

main.cpp

#include
#include
#include"backpack.h"
using namespace std;
//backpack problem
int main(){
int s = -1;
BackpackRunner * runner = new BackpackRunner();
try{

s = runner->run();

}catch(exception e){

    cout << "Exception while running main"<< e.what() << endl;

}

return s;

}