MI-PAA HW04 GA

                                                      #include <iostream>
#include <sstream>
#include <vector>
#include <algorithm>    // std::sort
#include <climits> //UINT_MAX
#include <cstdlib> //srand, rand
#include <ctime>


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

class ga_individual
 {
    public:
        vector<bool>    solution;
        int             fitness;
 };


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

vector< ga_individual > ga_generateInitialPopulation ( int initPopSize, int solutionSize )
 {
    vector<ga_individual> initPop;
    initPop . resize ( initPopSize );
    srand (time(NULL));

    for ( int i = 0; i < initPopSize; ++i )
     {
        initPop[i] . solution . resize ( solutionSize );
        for ( int j = 0; j < solutionSize; ++j )
         {
            initPop[i] . solution[j] = rand() % 2;
            //cout << initPop[i] . solution[j] << endl;
         }
     }
    return initPop;
 }

void ga_evaulateFitness ( vector<ga_individual>  & population, CInstance & instance )
 {
    for ( size_t i = 0; i < population . size(); ++i )
     {
        int cost = 0;
        int weight = 0;
        for ( size_t j = 0; j < population [0] . solution . size(); ++j )
         {
            if ( population[i] . solution [j] == true )
             {
                cost += instance . cost [j];
                weight += instance . weight [j];
             }
            if ( weight > instance . capacity )
                break;
         }
        if ( weight <= instance . capacity )
            population[i] . fitness = cost;
        else
            population[i] . fitness = 0;
     }
 }

bool compareGA_individualByFitness ( ga_individual a, ga_individual b )
 {
    return a . fitness > b . fitness;
 }

void ga_sortPopulationByFitness ( vector<ga_individual> & population )
 {
    sort ( population.begin(), population.end(), compareGA_individualByFitness );
 }

vector<ga_individual> ga_generateNewPopulation ( vector<ga_individual> & oldPopulation )
 {
    vector<ga_individual> newPopulation;
    newPopulation . resize ( oldPopulation . size() );
    newPopulation[0] = oldPopulation[0]; //preserve the best individual
    for ( size_t i = 1; i < newPopulation . size(); ++i )
     {
        newPopulation[i] . solution . resize ( oldPopulation[0] . solution . size() );
        for ( size_t j = 0; j < newPopulation[0].solution.size(); ++j )
         {
            if ( j < newPopulation[0].solution.size() / 2 )
             {
                newPopulation[i].solution[j] = oldPopulation[i] . solution[j];
             }
            else
             {
                newPopulation[i].solution[j] = oldPopulation[ (oldPopulation.size() / 2) - (i/2) ] . solution[j];
             }

         }
     }
    return newPopulation;
 }

// mutation probability, 0-100%
void ga_mutation ( vector<ga_individual> & population, int mutationProbability )
 {
    int upperBound = mutationProbability * (population . size() * population[0].solution.size() / 100.0);

    for ( size_t i = 0; i < upperBound ; ++i )
     {
            population[ 1 + (rand() % (population.size()-2) ) ].solution[ rand() % population[0].solution.size() ] = rand() % 2;
     }
 }

void printPopulation ( vector<ga_individual> & population )
 {
    for ( size_t i = 0; i < population . size(); ++i )
     {
        cout << "idx " << i << " fitness " << population[i].fitness << endl;
     }
    cout << endl;
 }

int ga_knapsack ( CInstance & instance, int initPopSize, int mutationProbability, int numberOfGenerations )
 {
    vector<ga_individual> population;
    population = ga_generateInitialPopulation ( initPopSize, instance . solution . size() );

    for ( int i = 0; i < numberOfGenerations; ++i )
     {

        ga_evaulateFitness ( population, instance );
        ga_sortPopulationByFitness ( population );

        cout << "id " << instance.id << " fitness " << population[0] . fitness << endl;
        //printPopulation ( population );

        population = ga_generateNewPopulation ( population );
        ga_mutation ( population, mutationProbability );
     }

    cout << endl;
    instance . solution = population[0] . solution;
    instance . total_cost = population[0] . fitness;
 }

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 );
    //instance, population size, mutation probability in %, number of generations
    ga_knapsack ( i, 100, 15, 1000 );
    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;
}