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