MI-PAA HW01 BruteForce

#include <iostream>
#include <sstream>
#include <vector>

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

     }
 }

/*
# let w[1], ... , w[n] be the weights of the items
# let v[1], ... , v[n] be the values of the items
# let maxWeight be the capacity of the knapsack

bestValue := 0

function solve(n, currentWeight, currentValue) {

    if n = 0 and currentWeight <= maxWeight and currentValue > bestValue:
        bestValue := currentValue

    if n = 0: return

    # don't pack this item
    solve(n-1, currentWeight, currentValue)
    # pack this item
    solve(n-1, currentWeight + w[n], currentValue + v[n])
}

solve(n, 0, 0)

print bestValue
*/


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 processInstance ( CInstance & i )
 {
    vector<bool> initSol ( i . solution );
    recursiveBruteForce ( i . quantity - 1, 0, 0, initSol, 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;
}