#include <stdio.h>
#include <malloc.h>
#include <sys/time.h>
#include <time.h>
#include <stdlib.h>
#include <math.h>

//#define MORE_THAN_32_THINGS

#define min(x,y) (x<y)?x:y

#define BRUTE_FORCE 0
#define RATIO_HEUR  1
#define RATIO_HEUR2  2
#define DYNAMIC_PROG 3
#define BRANCHING 4

struct timeval start_time;

struct thing
{
  int weight, price; //weight and price of thing in knapsack
  double rate;       // price / weight
  int belong;        // does belong thing to knapsack ? (ideal solution)
   int belong2;
   int best_belong;  
   int cummulative_price ; //cumulative price
};

struct result
{
   int price;
   int weight;
   int steps;
};


struct problem
{
  int id;
  int n;
  int M;
  struct thing *things;
  int ideal_price;      

   struct result results[5];
   struct problem *next;
};

int max_price;
int steps;

void init_time()
{
  gettimeofday(&start_time,0);
  steps=0;
}

long long int seconds_from_init()
{
  struct timeval current_time, result_time;
  gettimeofday(&current_time,0);
  result_time.tv_sec = current_time.tv_sec - start_time.tv_sec;
  result_time.tv_usec = current_time.tv_usec - start_time.tv_usec;
 
  while (result_time.tv_usec < 0) {
    result_time.tv_sec --;
    result_time.tv_usec +=1000000l;
  }

  return (long long int) ( result_time.tv_sec) * 1000000 + result_time.tv_usec;
}


void show_problems ( struct problem * problems)
{
  struct problem* problem_p;
  int i;

  for (problem_p = problems; problem_p !=NULL; problem_p = problem_p->next)
    {
      fprintf (stdout,"id %d \tn %d \tM %d ",problem_p->id, problem_p->n, problem_p->M);
      for (i = 0; i < problem_p-> n; i++)
	{
	  fprintf (stdout,"%d %d %lf ",problem_p->things[i].weight, problem_p->things[i].price, problem_p->things[i].rate);
	}
      fprintf (stdout,"Ideal price %d\n",problem_p->ideal_price);
      for (i = 0; i < problem_p-> n; i++)
	{
	  fprintf (stdout,"%d", problem_p->things[i].belong);
	}
      fprintf (stdout,"\n");
    }

}

/* void brute_force(struct problem *problem_p)
{
   int i;
   
#ifdef MORE_THAN_32_THINGS
   long long int combination, comb2, max_combination;
#else
   int combination, comb2, max_combination;
#endif
   int weight=0, price=0, best_price=0, best_weight=0;
   steps=0;

   max_combination = 1 << ( problem_p -> n ) ;

   for (combination = 1 ; combination <= max_combination - 1 ; combination++)
   {
      price=0; weight=0;

      comb2 = combination;

      for (i = 0; i < problem_p -> n && weight <= problem_p -> M; i++)
      {

         if ( (comb2 & 1) )
         {
            if (price > best_price)
            {
               best_price = price;
               best_weight = weight;
            }
            price += problem_p->things[i].price;
            weight += problem_p->things[i].weight;
	      
         }

         comb2 = comb2 >> 1;
      }

      steps++;

      if (price > best_price && weight <= problem_p-> M)
      {
         best_price = price;
         best_weight = weight;
      }

   }
  
   fprintf (stdout, "id %d Best price %d Best weight %d\n", problem_p -> id, best_price, best_weight);

   problem_p -> results[BRUTE_FORCE].price = best_price;
   problem_p -> results[BRUTE_FORCE].weight = best_weight;
   problem_p -> results[BRUTE_FORCE].steps = steps;
} */

int brute_force_recur(struct problem *problem_p, int knap, int actual_weight, int actual_price)
{
   int i;

   // founded better solution
   if (actual_price > max_price)
   {
      max_price = actual_price;

      for (i=0; i< problem_p->n; i++)
         problem_p->things[i].best_belong = problem_p->things[i].belong2;
   }

   if (knap < problem_p->n)
   {
      steps++;
      // if weight of thing is enough low to fit knapsack
      if ((actual_weight + problem_p->things[knap].weight) <= problem_p->M)
      {
         // we fill knapsack 
         problem_p->things[knap].belong2=1;
         // and trying recursively fill another thing
         brute_force_recur(problem_p, knap+1, actual_weight + problem_p->things[knap].weight, actual_price + problem_p->things[knap].price);
      }
      // unable to fit
      problem_p->things[knap].belong2=0;
      // we don't fill knapsack and trying recursively fill another thing
      brute_force_recur(problem_p, knap+1,actual_weight, actual_price);
   }
return 0;
}

void brute_force(struct problem *problem_p)
{
   int i;

   steps=0;

   for (i=0; i < problem_p->n ; i++)
   {
      // initially, we have no things in knapsack
      problem_p->things[i].belong2 = 0; 
      problem_p->things[i].best_belong = 0;
   }

   //the best price
   max_price = 0;

   brute_force_recur(problem_p, 0, 0, 0);

   fprintf (stdout, "id %d Best price %d\n", problem_p -> id, max_price);

   problem_p -> results[BRUTE_FORCE].price = max_price;
   problem_p -> results[BRUTE_FORCE].weight = 0;
   problem_p -> results[BRUTE_FORCE].steps = steps;
}


int ratio_heur(struct problem *problem_p)
{
   int i,j, max_i;
   double max;
   int weight=0, price=0;
   struct thing test_thing;
   struct thing *sorted_things;

   steps = 0;
   //sorting input data
   
   sorted_things = calloc (problem_p -> n, sizeof (struct thing));
   for (i = 0; i< problem_p ->n; i++)
      sorted_things[i] = problem_p->things[i];

   for (i=0 ; i < problem_p -> n - 1; i++)
   {
      max = sorted_things[i].rate; max_i = i;

      for (j=i ; j < problem_p -> n ; j++)
      {
         if ( sorted_things[j].rate > max ) { max = sorted_things[j].rate; max_i = j; }
	
         steps++;
      }
      if ( max_i != i) 
      {
         test_thing = sorted_things[max_i];
         sorted_things[max_i] = sorted_things[i];
         sorted_things[i] = test_thing;
      }
      steps++;
   }

   for (i = 0; i < problem_p-> n; i++)
   {
      if (weight + sorted_things[i].weight <= problem_p-> M)
      {
         price+=sorted_things[i].price;
         weight+=sorted_things[i].weight;
      }
      steps++;
   }
   free (sorted_things);

   fprintf (stdout, "id %d Best price %d Best weight %d\n",problem_p->id, price, weight);

   problem_p -> results[RATIO_HEUR].price = price;
   problem_p -> results[RATIO_HEUR].weight = weight;
   problem_p -> results[RATIO_HEUR].steps = steps;

   return problem_p->ideal_price - price;
}

int ratio_heur2(struct problem *problem_p)
{
   int i,j, max_i;
   double max;
   int weight=0, price=0;
   struct thing test_thing;

   struct thing *sorted_things;

   //sorting input data

   int valuable=0;
   steps = 0;

   sorted_things = calloc (problem_p -> n, sizeof (struct thing));

   for (i = 0; i< problem_p ->n; i++)
      sorted_things[i] = problem_p->things[i];

   //sorting input data

   for (i=0 ; i < problem_p -> n - 1; i++)
   {
      max = sorted_things[i].rate; max_i = i;

      for (j=i ; j < problem_p -> n ; j++)
      {
         if ( sorted_things[j].rate > max ) { max = sorted_things[j].rate; max_i = j; }
	
         steps++;
      }
      if ( max_i != i) 
      {
         test_thing = sorted_things[max_i];
         sorted_things[max_i] = sorted_things[i];
         sorted_things[i] = test_thing;
      }
      steps++;
   }

   // looking for the valuable thing
   for (i=0 ; i < problem_p -> n; i++)
   {
      if (sorted_things[valuable].price < sorted_things[i].price) valuable=i;
      steps++;
   }

   for (i = 0; i < problem_p-> n; i++)
   {
      if (weight + sorted_things[i].weight <= problem_p-> M)
      {
         price+=sorted_things[i].price;
         weight+=sorted_things[i].weight;	      
      }
      steps++;
   }

   //if price of the valuable thing is higher and weight of the valuable thing is  less than weight of knapsack

   if (sorted_things[valuable].price > price && sorted_things[valuable].weight <= problem_p->M)
      
   {
      price=sorted_things[valuable].price;
      weight=sorted_things[valuable].weight;
      fprintf (stdout,"Test the most of valuable thing applied - we can replace other things with the most valuable thing\n");
   }
   steps++;

   free(sorted_things);

   fprintf (stdout, "id %d Best price %d Best weight %d\n",problem_p->id, price, weight);

   problem_p -> results[RATIO_HEUR2].price = price;
   problem_p -> results[RATIO_HEUR2].weight = weight;
   problem_p -> results[RATIO_HEUR2].steps = steps;

   return problem_p->ideal_price - price;
}


int dynamic_prog(struct problem *problem_p)
{
   int sum_of_prices=0, sum_of_weights=0;
   int i,j;
   int *dynamic[2];

   steps = 0;
   
   for (i=0; i< problem_p->n; i++)
   {
      sum_of_prices+=problem_p->things[i].price;
      sum_of_weights+=problem_p->things[i].weight;
      steps++;
   }

   if ((dynamic[0] = calloc (sum_of_prices+1, sizeof(int)))==NULL)
   {
      fprintf (stderr,"Cannot allocate memory for dynamic\n");
      return -1;
   }
   if ((dynamic[1] = calloc (sum_of_prices+1, sizeof(int)))==NULL)
   {
      fprintf (stderr,"Cannot allocate memory for dynamic\n");
      return -1;
   }

   // W(0,0)=0
   dynamic[0][0]=0;
   // W(0,c) = infinitive for all prices >0
   for (j=1; j<=sum_of_prices ;j++)
      dynamic[0][j]=sum_of_weights+1;

   for (i=0 ; i<=problem_p->n; i++)
   {
      // for each price and i >1
      for (j=1; j<=sum_of_prices;j++)
      {
         // W(i+1,c) = min (W(i,c), W(i,c-c_(i+1)) + w_(i+1))
         // we have worse solution
         if (dynamic[(i+1)%2][j]!=0) steps++;

         if (j < problem_p->things[i].price)
            dynamic[(i+1)%2][j]=dynamic[i%2][j];
         else
            dynamic[(i+1)%2][j]=min(dynamic[i%2][j], 
                                    dynamic[i%2][j-problem_p->things[i].price] + problem_p->things[i].weight);
      }

   }

   i = problem_p->n;

   //looking for solution
   for (j=sum_of_prices;j>0; j--)
   {
      //we have solution
      if (dynamic[(i%2)][j] <= problem_p->M) 
      {
         fprintf (stdout, "id %d Best price %d Best weight %d\n",problem_p->id, j, dynamic[(i%2)][j]);

         problem_p -> results[DYNAMIC_PROG].price = j;
         problem_p -> results[DYNAMIC_PROG].weight = dynamic[(i%2)][j];
         problem_p -> results[DYNAMIC_PROG].steps = steps;

         free(dynamic[0]);
         free(dynamic[1]);
         return 0;
      }
      steps++;
   }
   fprintf (stderr,"Cannot find solutions\n");
   free(dynamic[0]);
   free(dynamic[1]);
   return 0;
}

int recursive_branch(struct problem *problem_p, int knap, int actual_weight, int actual_price)
{
   int i;
   steps++;

   // founded better solution
   if (actual_price > max_price)
   {
      max_price = actual_price;

      for (i=0; i< problem_p->n; i++)
         problem_p->things[i].best_belong = problem_p->things[i].belong2;
   }

   if ((knap < problem_p->n) && (actual_weight< problem_p->M) && (actual_price + problem_p->things[knap].cummulative_price > max_price))
   {
      // if weight of thing is enough low to fit knapsack
      if ((actual_weight + problem_p->things[knap].weight) <= problem_p->M)
      {
         // we fill knapsack 
         problem_p->things[knap].belong2=1;
         // and trying recursively fill another thing
         recursive_branch(problem_p, knap+1, actual_weight + problem_p->things[knap].weight, actual_price + problem_p->things[knap].price);
      }
      // unable to fit
      problem_p->things[knap].belong2=0;
      // we don't fill knapsack and trying recursively fill another thing
      recursive_branch(problem_p, knap+1,actual_weight, actual_price);
   }
   return 0;
}

void branch(struct problem *problem_p)
{
   int i,j;
   steps=0;

   for (i=0; i < problem_p->n ; i++)
   {
      problem_p->things[i].cummulative_price = 0;

      // initially, we have no things in knapsack
      problem_p->things[i].belong2 = 0; 
      problem_p->things[i].best_belong = 0;

      // computing cummulative price
      // for i-thing, cummulative price will be price[i] + price[i+1] .. + price[n]
      for (j=i; j < problem_p -> n; j++)
         problem_p->things[i].cummulative_price+=problem_p->things[j].price;
   }


   //the best price
   max_price = 0;

   recursive_branch(problem_p, 0, 0, 0);

  fprintf (stdout, "id %d Best price %d\n",problem_p->id, max_price);

   problem_p -> results[BRANCHING].price = max_price;
   problem_p -> results[BRANCHING].weight = 0;
   problem_p -> results[BRANCHING].steps = steps;
}


void print_statistics(struct problem *problem_p)
{
   double total_steps;

   total_steps = pow ( 2, problem_p->n);

      //if (problem_p->n > 25) init_step=1; else init_step=0;

          //         printf ("%s\t ",methods[i]);
          // printf ("\t%d\t%lf\t\t%d\t%lf\n",problem_p->results[i].price, (double)(abs(problem_p->results[i].price - problem_p->results[3].price)) *100 / problem_p->results[i].price, problem_p->results[i].steps,(double) ( problem_p->results[i].steps) * 100 / total_steps);

   fprintf(stderr,"%d\t",problem_p->id);

          // brute force
      if (problem_p->n > 25) fprintf (stderr, "NA\t"); else
         fprintf (stderr,"%lf", (double) (problem_p -> results[BRUTE_FORCE].steps) * 100 / total_steps);

      // heuristiky
      fprintf (stderr,"\t%lf\t%lf\t%lf\t%lf", (double) (problem_p -> results[RATIO_HEUR].steps) * 100 / total_steps, (double) ( abs (problem_p->results[RATIO_HEUR].price - problem_p->results[DYNAMIC_PROG].price)) * 100 / problem_p->results[DYNAMIC_PROG].price, (double) (problem_p -> results[RATIO_HEUR2].steps) * 100 / total_steps, (double) (abs (problem_p->results[RATIO_HEUR2].price - problem_p->results[DYNAMIC_PROG].price)) * 100 / problem_p->results[DYNAMIC_PROG].price);
      
      // dynamic programming
      fprintf (stderr,"\t%lf\t%lf\n",(double) (problem_p -> results[DYNAMIC_PROG].steps) * 100 / total_steps, (double) (problem_p -> results[BRANCHING].steps) * 100 / total_steps);
}

int main(int argc, char *argv[])
{
   struct problem *problems=NULL, *problems_p=NULL;
   struct thing *thing_p;
   long long int brute_force_time, heuristic_rate_time, heuristic_rate_time2, branching_time, dynamic_prog_time;

   // input file and result file
   FILE *fi;
   int i;
   int id, n, M;

   int deviation, max_deviation=0, cumulative_deviation=0;
   int deviation2, max_deviation2=0, cumulative_deviation2=0;
   int brute_steps, branching_steps, rate_steps, rate2_steps, dynamic_steps;

   if (argc < 2 )
   {
      fprintf (stdout, "Usage: %s input_data\n",argv[0]);
      return 0;
   }

   if ( ( fi = fopen (argv[1],"r")) == NULL) { 
      fprintf (stderr, "Cannot open input file %s\n",argv[1]);
      return -1;
   }

   while (! feof (fi))
   {
      fscanf (fi, "%d %d %d", &id, &n, &M);
/*      fscanf (ri, "%d %d %d", &idr, &nr, &ideal_price);
        if (id!=idr || n != nr) 
        {
        fprintf (stderr, "Input data doesn't match solution\n");
        return -2;
        }*/
      if (feof(fi)) break;

      // pokym citame hned prvy problem
      if (problems == NULL) {
         problems = malloc (sizeof (struct problem) + 1);
         problems_p = problems; 
      } else 
      {
         problems_p->next = malloc (sizeof (struct problem) + 1);
         problems_p = problems_p->next;
      }

      // nastavime jednotlive polozky
      problems_p -> id = id;
      problems_p -> n = n;
      problems_p -> M = M;
//      problems_p -> ideal_price = ideal_price;
      problems_p -> ideal_price = 0;
      problems_p -> things = calloc (n, sizeof (struct thing));

      thing_p = problems_p -> things;
      for (i = 0; i < problems_p -> n; i++)
      {
         fscanf (fi, "%d %d", &thing_p[i].weight, &thing_p[i].price);
         thing_p[i].rate = (double) (thing_p[i].price ) /  thing_p[i].weight;
         //  fscanf (ri, "%d", &thing_p[i].belong);
      }
      
   }
   problems_p->next =0;
   if (problems == NULL) { fprintf (stderr, "No input data read.\n"); return -3; }
//  show_problems (problems);

   fprintf (stdout,"\n***** Brute-force computing *****\n");

   if ( problems_p -> n < 26)
   {

      init_time();

      for (problems_p = problems; problems_p !=NULL; problems_p=problems_p->next)
         brute_force(problems_p);

      brute_force_time = seconds_from_init();
      brute_steps = steps;

   }
   else
   {
      fprintf (stdout,"n > 26, skipping brute force...\n");
      brute_force_time=-1;
      brute_steps = -1;
   }


         fprintf (stdout,"\n***** Branching computing *****\n");

   init_time();
   for (problems_p = problems; problems_p !=NULL; problems_p=problems_p->next)
      branch(problems_p);

   branching_time = seconds_from_init();
   branching_steps = steps;

   fprintf (stdout,"\n***** Dynamic programming *****\n");

   init_time();
   for (problems_p = problems; problems_p !=NULL; problems_p=problems_p->next)
      dynamic_prog(problems_p);

   dynamic_prog_time = seconds_from_init();
   dynamic_steps = steps;

   fprintf (stdout,"\n***** Rate-heuristic computing *****\n");
  
   init_time();

   for (problems_p = problems; problems_p !=NULL; problems_p=problems_p->next)
   {
      deviation = ratio_heur(problems_p);
      if (deviation > max_deviation) max_deviation = deviation;
      cumulative_deviation +=deviation;    
   }

   heuristic_rate_time = seconds_from_init();
   rate_steps = steps;

   fprintf (stdout,"\n***** Rate-heuristic computing with the most valuable thing *****\n");
  
   init_time();

   for (problems_p = problems; problems_p !=NULL; problems_p=problems_p->next)
   {
      deviation2 = ratio_heur2(problems_p);
      if (deviation2 > max_deviation2) max_deviation2 = deviation2;
      cumulative_deviation2 +=deviation2;    
   }

   heuristic_rate_time2 = seconds_from_init();
   rate2_steps = steps;

   fprintf (stdout,"ID\tBrute force\tHeuristics\tHeur.error\tHeuristics2\tHeur2. error\tDynamic program\tBranching\n");
   for (problems_p = problems; problems_p !=NULL; problems_p=problems_p->next)
   {
      print_statistics(problems_p);
   }

/*
   fprintf (stdout, "\n***** RESULT *****\n");
   fprintf (stdout, "Brute-force:\n\tTotal time: %lld us\n",brute_force_time);
   fprintf (stdout,"\nBranching\n\tTotal time: %lld us\n",branching_time);
   fprintf (stdout,"\nDynamic programming\n\tTotal time: %lld us\n",dynamic_prog_time);
   fprintf (stdout, "\nRate-heuristic\n\tTotal time %lld us\n", heuristic_rate_time);
   fprintf (stdout, "\t\tNumber of things: %d\t Cumulative deviation %d\n",problems->n, cumulative_deviation);
   fprintf (stdout, "\t\tAverage error=%lf\tMaximum error=%d\n",(double)(cumulative_deviation)/problems->n, max_deviation);

   fprintf (stdout, "\nRate-heuristic with the valuable things\n\tTotal time %lld us\n", heuristic_rate_time2);
   fprintf (stdout, "\t\tNumber of things: %d\t Cumulative deviation %d\n",problems->n, cumulative_deviation2);
   fprintf (stdout, "\t\tAverage error=%lf\tMaximum error=%d\n",(double)(cumulative_deviation2)/problems->n, max_deviation2);
*/

   return 0;
}