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 delt...