#include "class_knap_sack_input.cpp"

/* batoh */
CKnapSackInput *sack;

/* pocet vypocetnich kroku */
int steps;

/* maximum */
int max(int a, int b) {
    return (a > b) ? a : b;
}

/* ------------------------------------------------------- */

/* dynamicky */
int solve_dp() {
    int bestcost[MAXWEIGHT + 1];
    for(int i = 0; i <= MAXWEIGHT; i++) bestcost[i] = 0;

    // pro kazdy predmet
    for(int i = 0; i < sack->getItems(); i++) {
        // pro kazdy "podbatoh"
        for(int w = sack->getMaxWeight(); w > 0; --w) {
            steps++;
            if(sack->getItem(i).weight <= w) {
                bestcost[w] = max(
                    bestcost[w],
                    bestcost[w - sack->getItem(i).weight] + sack->getItem(i).cost
                );
            }
        }
    }
    return bestcost[sack->getMaxWeight()];
}

/* ------------------------------------------------------- */

/* branch and bounds */
int solve_bb() {
    // konfigurace reseni
    int config[MAXITEMS], best_config[MAXITEMS];
    for(int i=0; i<MAXITEMS; i++) config[i] = 0;

    int solution_cost = 0;
    int load = 0;
    int cost = 0;
    int index = 0;

    int accumulated_costs[MAXITEMS];
    int sum = 0;
    for(int i=sack->getItems()-1; i>-1; i--) {
        sum += sack->getItem(i).cost;
        accumulated_costs[i] = sum;
    }

    // samotne reseni
    int cont = 1;
    while(cont) {
        // descend
        for(; index < sack->getItems(); index++) {
            steps++;
            // muzu pridat item cislo index?
            if(((load + sack->getItem(index).weight) <= sack->getMaxWeight()) && (!config[index])) {
                // ano, pridam ho
                config[index] = 1;
                load += sack->getItem(index).weight;
                cost += sack->getItem(index).cost;
            } else if((cost + accumulated_costs[index + 1]) <  solution_cost) {
                goto mount;
            }
        }
        index--;

        // mam lepsi nez dosavadni reseni?
        if(cost > solution_cost) {
            // ano...
            solution_cost = cost;
            for(int i=0; i < sack->getItems(); i++) {
                best_config[i] = config[i];
            }
        }

        mount:
        int reached1 = 0;

        // vyrad z reseni posledni item
        if(config[index]) {
            config[index] = 0;
            load -= sack->getItem(index).weight;
            cost -= sack->getItem(index).cost;
        }

        // Mount until an included item found or the beginning of config[] reached.
        while(!reached1 && (index > 0)) {
            index--;
            steps++;
            if((config[index])) {
                if(!((cost - sack->getItem(index).cost + accumulated_costs[index+1]) <  solution_cost)) {
                    reached1 = 1;
                }
                config[index] = 0;
                load -= sack->getItem(index).weight;
                cost -= sack->getItem(index).cost;
            }
        }

        index++;
        cont = reached1;
    }

    return solution_cost;
}

/* ------------------------------------------------------- */

/* heuristika cena/vaha */
int solve_hr() {
    double heuristic[MAXITEMS];
    int solution[MAXITEMS];
    for(int i=0; i<sack->getItems(); i++) {
        heuristic[i] = double(sack->getItem(i).cost) / double(sack->getItem(i).weight);
        solution[i] = 0;
    }

    // hledej nejvyhodnejsi dosud nepouzite itemy
    int mass = 0;
    int konec = 0;
    int cost = 0;

    while(!konec) {
        float h = 0;
        int j = -1;
        konec = 1;

        // j <- index dalsiho dosud nepouziteho nejvyhodnejsiho prvku
        for(int i=0; i<sack->getItems(); i++) if(!solution[i] && heuristic[i] > h && (sack->getItem(i).weight + mass) < sack->getMaxWeight()) {
            j = i;
            h = heuristic[i];
            konec = 0;
        }
        
        // prvek byl skutecne nalezen?
        if(!konec) {
            solution[j] = 1;
            mass += sack->getItem(j).weight;
            cost += sack->getItem(j).cost;
        }

        steps++;
    }
    
    return cost;
}

/* main */
int main(int argc, char *argv[]) {
    if(argc == 0) return -1;

    int avg_dp, avg_bb, avg_hr;
    int avgs_dp, avgs_bb, avgs_hr;
    int cost, n;

    avg_dp = avg_bb = avg_hr = 0;
    avgs_dp = avgs_bb = avgs_hr = 0;
    n = 0;

    sack = new CKnapSackInput(argv[1]);
    while(sack->loadNext()) {
        n++;

        steps = 0;
        cost = solve_dp();
        avg_dp += cost;
        avgs_dp += steps;
//        cout << "DP " << cost << "; ";

        steps = 0;
        cost = solve_bb();
        avg_bb += cost;
        avgs_bb += steps;
//        cout << "BB " << cost << "; ";

        steps = 0;
        cost = solve_hr();
        avg_hr += cost;
        avgs_hr += steps;
//        cout << "HR " << cost << "; ";

//        cout << endl;
    }

    cout << "prumerna cena - ";
    cout << "DP - " << (avg_dp / n) << " ";
    cout << "BB - " << (avg_bb / n) << " ";
    cout << "HR - " << (avg_hr / n) << " ";
    cout << endl;

    cout << "prumerne kroky - ";
    cout << "DP - " << (avgs_dp / n) << " ";
    cout << "BB - " << (avgs_bb / n) << " ";
    cout << "HR - " << (avgs_hr / n) << " ";
    cout << endl;

    return 0;
}