MI-PAA HW02 BB, DP, FPTAS

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


using namespace std;

class CInstance
 {
    public:
        vector<unsigned int>    weight;
        vector<unsigned int>    cost;
        vector<bool>            solution;
        unsigned int            id;
        unsigned int            quantity;
        unsigned int            capacity;
        unsigned 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 << (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;

 }



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

int branchAndBound ( 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;

    // bb enchancement start
    int remainingItemsSumCost = 0;
    for ( size_t tmp = 0; tmp <= n; ++tmp )
        remainingItemsSumCost += i . cost [ tmp ];

    if ( i . total_cost > currentValue + remainingItemsSumCost )
        return 0;

    if ( currentWeight > i . capacity )
        return 0;
    // bb enhancement end


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

    //pack this
    s [ n ] = true;
    branchAndBound ( 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, ie 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 dynamicAlg ( CInstance & instance )
 {
    int ** table = new int * [ instance . weight . size() + 1 ];
    for(int i = 0; i < instance . weight . size() + 1; ++i)
        table[i] = new int[ instance . capacity + 1 ];

    vector< vector< vector<bool> > > solutions;

    solutions . resize ( instance . weight . size() + 1 );
    for ( size_t i = 0; i < instance . weight . size() + 1; ++i )
     {
        solutions[i] . resize ( instance . capacity + 1 );
        for ( size_t j = 0; j < instance . capacity + 1; ++j )
           solutions[i][j] . resize ( instance . weight . size() + 1, false);
     }

    for ( unsigned int i = 0; i <= instance . weight . size(); ++i )
     {
        for ( unsigned int j = 0; j <= instance . capacity; ++j )
         {
            if ( i == 0 || j == 0 )
             {
                table[i][j] = 0;
             }
            else if ( instance . weight [ i - 1 ] <= j )
             {
                if ( instance.cost[i-1] + table[i-1][j-instance.weight[i-1]] > table[i-1][j] )
                 {
                    table[i][j] = instance.cost[i-1] + table[i-1][j-instance.weight[i-1]];
                    solutions[i][j] = solutions[i-1][j - instance.weight[i-1]];
                    solutions[i][j][i-1] = true;
                 }
                else
                 {
                    table[i][j] = table[i-1][j];
                    solutions[i][j] = solutions[i-1][j];

                 }
             }
            else
             {
                table[i][j] = table[i-1][j];
                solutions[i][j] = solutions[i-1][j];

             }
         }
     }

    instance . total_cost = table [ instance . weight . size() ] [ instance . capacity ];
    instance . solution = solutions [ instance . weight . size() ] [ instance . capacity ];

    for(int i = 0; i < instance . weight . size() + 1; ++i)
        delete[] table[i];
    delete[] table;

    return 0;
 }

unsigned int maxCost ( CInstance & instance )
 {
    unsigned int cmax = 0;
    for ( size_t i = 0; i < instance . cost . size(); ++i )
        if ( instance . cost [ i ] > cmax )
            cmax = instance . cost [ i ];
    return cmax;
 }

unsigned int maxWeight ( CInstance & instance )
 {
    unsigned int wmax = 0;
    for ( size_t i = 0; i < instance . weight . size(); ++i )
        if ( instance . weight [ i ] > wmax )
            wmax = instance . weight [ i ];
    return wmax;
 }

unsigned int sumOfInstanceCosts ( CInstance & instance )
 {
    unsigned int sum = 0;
    for ( size_t i = 0; i < instance . cost . size(); ++i )
     {
        sum += instance . cost [ i ];
     }
    return sum;
 }

int fptas ( CInstance & instance, double eps )
 {

     /* ------------------ FPTAS MODIFICATIONS START ------------------*/

    unsigned int cmax = maxCost ( instance );
    double k = (eps * cmax) / instance . cost . size();

    vector<unsigned int> cost_backup;
    cost_backup . resize ( instance . cost . size() );
    for ( size_t i = 0; i < instance . weight . size(); ++i )
     {
        cost_backup [ i ] = instance . cost [ i ];
        instance . cost [ i ] = instance . cost [ i ] / k;
        //instance . cost [ i ] = instance . cost [ i ] / 4;
     }

    unsigned int wmax = maxWeight ( instance );
    /* ------------------ DECLARATIONS START ------------------*/

    unsigned int sumOfCosts = sumOfInstanceCosts ( instance );

    unsigned int ** table = new unsigned int * [ instance . cost . size() + 1 ];
    for(size_t i = 0; i < instance . cost . size() + 1; ++i)
        table[i] = new unsigned int[ sumOfCosts + 1 ];

    vector< vector< vector<bool> > > solutions;

    solutions . resize ( instance . cost . size() + 1 );
    for ( size_t i = 0; i < instance . cost . size() + 1; ++i )
     {
        solutions[i] . resize ( sumOfCosts + 1 );
        for ( size_t j = 0; j < sumOfCosts + 1; ++j )
           solutions[i][j] . resize ( sumOfCosts + 1, false);
     }


    /* ------------------ COMPUTATION START ------------------*/

    for ( size_t i = 0; i <= instance . cost . size(); ++i )
     {
        for ( unsigned int j = 0; j <= sumOfCosts; ++j )
         {
            if ( i == 0 )
             {
                if ( j == 0 )
                    table[i][j] = 0;
                else
                    table[i][j] = UINT_MAX - wmax - 10;
             }
            else if ( instance . cost [ i - 1 ] <= j )
             {
                if ( instance.weight[i-1] + table[i-1][j-instance.cost[i-1]] < table[i-1][j] )
                 {
                    table[i][j] = instance.weight[i-1] + table[i-1][j-instance.cost[i-1]];
                    solutions[i][j] = solutions[i-1][j - instance.cost[i-1]];
                    solutions[i][j][i-1] = true;
                 }
                else
                 {
                    table[i][j] = table[i-1][j];
                    solutions[i][j] = solutions[i-1][j];

                 }
             }
            else
             {
                table[i][j] = table[i-1][j];
                solutions[i][j] = solutions[i-1][j];

             }
         }
     }

    /* ------------------ BEST SOLUTION SELECTION ------------------*/

    unsigned int maxIndex = 0;
    for ( size_t i = 0; i < sumOfCosts; ++i )
     {
        if ( table[ instance.cost.size() ] [ i ] < instance . capacity )
            maxIndex = i;
     }
    instance . solution = solutions [ instance . cost . size() ] [ maxIndex ];

    /* ------------------ SOLUTION COST COMPUTATION ------------------*/

    instance . total_cost = 0;
    for ( size_t i = 0; i < instance . cost . size(); ++i )
     {
        if ( instance . solution[ i ] )
            instance . total_cost += cost_backup [ i ];
     }

    /* ------------------ CLEANUP ------------------*/

    for(size_t i = 0; i < instance . weight . size() + 1; ++i)
        delete[] table[i];
    delete[] table;

    return 0;
 }

int processInstance ( CInstance & i )
 {
    //vector<bool> initSol ( i . solution );
    //recursiveBruteForce ( i . quantity - 1, 0, 0, initSol, i );
    //greedyHeuristic ( i );
    //branchAndBound ( i . quantity - 1, 0, 0, initSol, i );
    //dynamicAlg ( i );
    fptas ( i, 0.3 );
    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;
}