#include <cstdlib>
#include <iostream>
#include <time.h>
#include <math.h>

using namespace std;

const int maxVeci=40;

FILE *src,*dest;

int n;   // pocet veci
int M;   // kapacita batohu
int V[maxVeci]; // hmotnosti veci
int C[maxVeci]; // ceny veci
int nr[maxVeci]; // originalni posloupnost prvku
int id; // id zadani

bool maska[maxVeci]; // bitova maska pro bruteforce

bool inKnap[maxVeci]; // je v batohu
int knapPrice=0;  // cena veci v batohu
int knapWeight=0; // vaha v batohu
time_t timeStart,timeEnd;

class tFronta {
  int f,l;
  int fronta[maxVeci];
  public:
    void Init(void) {f=0;l=0;}
    tFronta(void) {Init();}
    bool IsEmpty(void) {if (f==l) return true; else return false;}
    void Push(int a) {
      if (f>=maxVeci) f=0;
      fronta[f++]=a;
    }
    int Pop(void) {
      if (l>=maxVeci) l=0;
      return fronta[l++];
    }
} queue;

class tStack {
  int f;
  int fronta[maxVeci];
  public:
    void Init(void) {f=0;}
    tStack(void) {Init();}
    bool IsEmpty(void) {if (f==0) return true; else return false;}
    bool IsFull(void) {if (f==maxVeci) return true; else return false;}
    void Push(int a) {if (f<maxVeci) fronta[f++]=a;}
    int Pop(void) {if (f>0) return fronta[--f];}
} stack;

void BruteForceComb(int comb=0) {
  for (int i=0; i<n; i++) {
    if (comb & (1<<i)) maska[i]=true;
    else maska[i]=false;
  }
}

void BruteForce(void) {
  int combs;
  int weight, price;
  int maxPrice, maxComb;
  
  maxPrice=0;
  
  combs=(int) pow(2,n);
  for (int i=0; i<combs; i++) {
    weight=0;
    price=0;
    BruteForceComb(i);
    for (int j=0; j<n; j++) {
      if ((V[j]+weight<M) && maska[j])
      {
        weight+=V[j];
        price+=C[j];
      }
    }
    if (maxPrice<price) {
      maxComb=i;
      maxPrice=price;
    }
  }
  
  BruteForceComb(maxComb);
  for (int j=0; j<n; j++) {
    if ((V[j]+knapWeight<M) && maska[j])
    {
      knapWeight+=V[j];
      knapPrice+=C[j];
      inKnap[j]=true;
    } else inKnap[j]=false;
  }
  
}

void Sort() {
	int i, j, tmp;
	
	for (i=0; i<n; i++) {
		for (j=n-1; j>=i; j--) {
      if ((C[j]/V[j]) > (C[i]/V[i])) {
        tmp=V[j];V[j]=V[i];V[i]=tmp;
	      tmp=C[j];C[j]=C[i];C[i]=tmp;
        tmp=nr[j];nr[j]=nr[i];nr[i]=tmp;
      }
		}
  }
}

void Greedy(void) {
	for (int i=0; i<n; i++) {
    if ((knapWeight+V[i])<=M)
    {
      knapPrice+=C[i];
      knapWeight+=V[i];
      inKnap[i]=true;
    } else inKnap[i]=false;
  }
}

int main(int argc, char *argv[])
{
  bool bruteForce=1;  // pouzit silu nebo greedy
  char str[20];

  printf("Knapsack problem 2005 by GS.\n");
  printf("Possible parameters: [bruteforce | greedy]\n");
  printf("Input file: knap_[0-99].txt\n");
  printf("Output file: output_[0-99].txt\n");
  printf("\n");
  
  if ((argc>1) && ((!strcmp(argv[1],"bruteforce")) || (!strcmp(argv[1],"force")))) bruteForce=1;
  else if ((argc>1) && (!strcmp(argv[1],"greedy"))) bruteForce=0;
  
  if (bruteForce) printf("Using bruteforce....\n");
  else printf("Using greedy algorythm sorted by price/weight....\n");
  printf("\n");

  for (int i=0; i<=99; i++) {
    sprintf(str,"knap_%d.txt",i);
    if ((src=fopen(str,"r"))==NULL) continue;
    sprintf(str,"output_%d.txt",i);
    if ((dest=fopen(str,"w"))==NULL) {
      fclose(src);
      continue;
    }
    for (int rad=0; rad<50; rad++) {
      knapWeight=0;
      knapPrice=0;

      // nacteni dat ze souboru				
      fscanf(src,"%d ",&id);  // id
      fscanf(src,"%d ",&n);  // pocet veci
      fscanf(src,"%d ",&M);  // kapacita batohu
      if (n>maxVeci) {
        printf("Warning: maxitems overloaded. Using only %d items.\n",maxVeci);
        n=maxVeci;
      }
      for (int j=0;j<n;j++) {
		    fscanf(src,"%d ",&V[j]);
        fscanf(src,"%d ",&C[j]);
        inKnap[j]=false;
        nr[j]=j+1;
      }
  
      timeStart=time(NULL);
      if (bruteForce) BruteForce();
      else {
        Sort();
        Greedy();
      }
      timeEnd=time(NULL);
  
      if (dest) fprintf(dest,"%d %d %d %d\n",id,n,knapPrice,timeEnd-timeStart);  
    }
    fclose(dest); 
  }
  // system("PAUSE");
  return EXIT_SUCCESS;
}