MI-PAA HW01 GreedyHeuristic

#include <iostream>
#include <sstream>
#include <vector>
#include <algorithm>    // std::sort


using namespace std;

class CInstance
 {
    public:
        vector<unsigned int>    weight;
        vector<unsigned int>    cost;
        vector<bool>            solution;
        int                     id;
        int                     quantity;
        int                     capacity;
        int                     total_cost;
 };


int readInstance ( CInstance & i, string line )
 {
    int tmp;
    stringstream ss;
    ss << line;

    ss >> i . id;
    ss >> i . quantity;
    ss >> i . capacity;
    for ( int a = 0; a < i . quantity; ++a )
     {
        ss >> tmp;
        i . weight . push_back ( tmp );
        ss >> tmp;
        i . cost . push_back ( tmp );
     }
    i . solution . resize ( i . weight . size(), false );
    return 0;
 }

int printInstance ( CInstance & i )
 {
    cout << i . id << " " << i . quantity << " " << i . capacity << " ";

    for ( int a = 0; a < i . quantity; ++a )
     {
        cout << i . cost [ a ] << " " << i . weight [ a ] << " ";
     }
    cout << endl;
    return 0;
 }

int printSolution ( CInstance & i )
 {
    cout << i . id << " " << i . quantity << " " << i . total_cost << "  ";

    for ( int a = 0; a < i . quantity; ++a )
     {
         //cout << ( i . solution [ a ] ? "0" : "1" ) << " ";
         cout << (int) i . solution [ a ] << " ";
     }
    cout << endl;
 }

int countInstanceCost ( CInstance & i )
 {
    int tmp_cost = 0;
    for ( size_t idx = 0; idx < i . cost . size(); ++idx )
        if ( i . solution [ idx ] )
            tmp_cost += i . cost [ idx ];
    return tmp_cost;

 }

//broken / unfinished
int countNextSolution ( CInstance & i )
 {

    for ( size_t idx = 0; idx < i . solution . size(); ++idx )
     {
        if ( i . solution [ idx ] == false )
         {
            i . solution [ idx ] = true;
            return 0;
         }

     }
 }


int recursiveBruteForce ( int n, int currentWeight, int currentValue, vector<bool> s, CInstance & i )
 {
    if ( n == -1 && currentWeight <= i . capacity && currentValue > i . total_cost )
     {
        i . total_cost = currentValue;
        for ( size_t idx = 0; idx < i . solution . size(); ++idx )
            i . solution [ idx ] = s [ idx ];
     }

    if ( n == -1 )
        return 0;

    //dont pack this
    s [ n ] = false;
    recursiveBruteForce ( n-1, currentWeight, currentValue, s, i );

    //pack this
    s [ n ] = true;
    recursiveBruteForce ( n-1, currentWeight + i . weight [ n ], currentValue + i . cost [ n ], s, i );
 }

bool compareIdValuePairbyValue ( pair<int,double> a, pair<int,double> b )
 {
    return ( a . second > b . second );
 }


int greedyHeuristic ( CInstance & i )
 {
    vector< pair<int,double> > ratio;
    ratio . resize ( i . quantity );
    for ( size_t idx = 0; idx < i . quantity; ++ idx )
     {
        ratio [ idx ] . first = idx;
        ratio [ idx ] . second = (double) i . cost [ idx ] / (double) i . weight [ idx ]; //suppose positive weights...
     }

    //high to low, is best to worst
    sort ( ratio.begin(), ratio.end(), compareIdValuePairbyValue );

    int currentWeight = 0;
    i . total_cost = 0;
    for ( size_t idx = 0; idx < i . quantity; ++ idx )
     {
        if ( currentWeight +  i . weight [ ratio [ idx ] . first ] <= i . capacity ) // another item still fits
         {
            currentWeight +=  i . weight [ ratio [ idx ] . first ];
            i . total_cost += i . cost [ ratio [ idx ] . first ];
            i . solution [ ratio [ idx ] . first ] = true;
         }
     }

 }

int processInstance ( CInstance & i )
 {
    vector<bool> initSol ( i . solution );
    //recursiveBruteForce ( i . quantity - 1, 0, 0, initSol, i );
    greedyHeuristic ( i );
    return 0;
 }

int main ( int argc, char ** argv )
{
    string line;
    vector<CInstance> instances;
    while ( getline ( cin, line ) )
     {
        instances . resize ( instances . size () + 1 );
        readInstance ( instances [ instances . size () - 1 ], line );
     }

    for ( size_t i = 0; i < instances . size(); ++i )
     {
        processInstance ( instances [ i ] );
     }

    for ( size_t i = 0; i < instances . size(); ++i )
     {
        printSolution ( instances [ i ] );
     }


    return 0;
}