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

using namespace std;

#define maxVeci 40	// max veci v batohu
#define maxVaha 5999	// max vaha batohu
#define constK 4		// k pro kombinovanou heuresticu

FILE *src,*dest,*krok;
unsigned int stepNr=0;	// pocet zkoumanejch kroku

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;	// mereni casu

int maxComb;	// pocet kombinaci pro bruteforce a k-tice
int combinations[constK];	// prave pouzivana ktice

bool actInKnap[maxVeci]; //aktualni reseni
int actPrice,actMaxTeor,actWeight; //aktualni parametry

int pole[maxVeci][maxVaha]; //pole cen pro dynamickou verzi (max. 40 polozek pro instanci, maximalni nosnost batohu 999)

//---------------------------------------------------------------------------------

void BruteForceComb(int comb=0) {
  for (int i=0; i<n; i++) {

    if (comb & (1<<i)) maska[i]=true;
    else maska[i]=false;

	stepNr++;
  }
}

void BruteForce(void) {
  int combs;
  int weight, price;
  int maxPrice;
  
  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];
      }
			stepNr++;
    }
    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;
	 stepNr++;
  }
}

//---------------------------------------------------------------------------------

void SortRate() {
	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;
      }
			stepNr++;
		}
  }
}

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;

		stepNr++;
	}
}

//---------------------------------------------------------------------------------

void ChooseExpensive() {
	int maxPrice=0;
	for (int i=1; i<n; i++) {
		if (C[i]>C[maxPrice]) maxPrice=i;
		stepNr++;
	}
	if (knapPrice<C[maxPrice]) {
		knapPrice=C[maxPrice];
		knapWeight=V[maxPrice];
		for (int i=0; i<n; i++) inKnap[i]=false;
		inKnap[maxPrice]=true;
	}
}

//---------------------------------------------------------------------------------

int ComputePrices(int n, int space) { // n = zbyva predmetu; space - zbyva mista
	int with, without;
	int pol=n-1; // prepocet z mnozstvi na index pole

	stepNr++;

	if (space<=0 || n==0) return 0; // nic se nevejde nebo uz neni co pridat - > skoncili jsme rekurzi

	if (pole[n][space]!=-maxVaha) return (pole[n][space]); // vyresena mista uz neresime a vratime co uz bylo vyreseno
		
	if (V[pol]>space) pole[n][space]=ComputePrices(pol,space); // nevejde se tam, vlozim moznost bez prvku
	else {  // vejde -> vlozim lepsi moznost
		with=C[pol]+ComputePrices(pol,space-V[pol]);  // moznost s prvkem
		without=ComputePrices(pol,space); // moznost bez prvku
		if (with>without) {
			pole[n][space]=with;
			return (with);
		} else {
			pole[n][space]=without;
			return (without);
		}
	}
	return (pole[n][space]);
}

void Dynamic() {
	int i, j;
	
	for (i=0; i<maxVeci; i++) // vymazani pole
		for (j=0; j<maxVaha; j++)
			pole[i][j]=-maxVaha;
	for (i=0; i<n; i++) // 0 v 1nim radku
		pole[i][0]=0;
	for (i=0; i<M; i++) // 0 v prvnim sloupci
		pole[0][i]=0;
	
	knapPrice=ComputePrices(n, M);
	int vaha=M;
	int pol;

	//zpetny prochazeni stromu k dohledani predmetu co jsou v batohu
	for (i=n; i>=1; i--) {
		pol=i-1;	// prepocet z poctu na index
		if (pole[i][vaha]!=pole[pol][vaha]) {
			inKnap[pol]=true;
			vaha=vaha-V[pol];
		} else inKnap[pol]=false;
	}
}

//---------------------------------------------------------------------------------

void DoBest(void) {
	int actPrice = 0;

	for (int i=0; i<n; i++)
		if (actInKnap[i]) actPrice=actPrice+C[i];

	if (actPrice>knapPrice) {
		knapPrice=actPrice;
		for (int i=0; i<n; i++)
			inKnap[i]=actInKnap[i];
	}
}

void RecountTeor(int kam)
{
	int i;
	int actWeight=0;

	actMaxTeor=0;
	for (i=0; i<kam; i++) {
		if (actInKnap[i]) {
			actWeight+=V[i];
			actMaxTeor+=C[i];
		}
		stepNr++;

	}
	for (i=kam; i<n; i++) {
		if (actWeight+V[i]<=M) {	// vypocteme maximalni teoretickou cenu batohu
				actWeight+=V[i];
				actMaxTeor+=C[i];
		} else {	// tenhle predmet uz se tam nevejde, tak zapocitame jen cast ktera se tam vejde a dalsi uz cpat nebudem
			actMaxTeor+=((M-actWeight)*C[i]/V[i]+1);
			break;
		}
	}
}

void Branches(int item, int space)
{
	stepNr++;
	if (space<=0) return;	// tenhle predmet se tam uz nevejde
	RecountTeor(item);
	if (actMaxTeor<knapPrice) return;	// maximalni teoreticka cena vetve je nizsi nez zatim nejlepsi,neresit
	if (item==n) {	// byl posledni predmet, zjistit jestli nejlepsi reseni
		DoBest();
		return;
	}
	actInKnap[item]=true;
	Branches(item+1,space-V[item]);
	actInKnap[item]=false;
	Branches(item+1,space);
}

//---------------------------------------------------------------------------------

int NnadK(int n, int k) {
  int f=1;
  for (int i=0; i<k; i++) {
    f*=n-i;
    f/=i+1;
  }
  return f;
}

void NextKtice(int n, int k) {	// generovani k-tic
  if (k==0) return;
  combinations[k-1]++;
  if ((combinations[k-1] % n)==0) {
    NextKtice(n-1, k-1);
    combinations[k-1]=combinations[k-2]+1;
  }
}

void HeuresticKtic(void)
{
	int i;
	
   SortRate();
    
	maxComb=NnadK(n,constK);	// pocet k-tic
    
   for (i=0; i<constK; i++) combinations[i]=i;	// prvni k-tice: 0 1 2 3 .. k-1
    
   for (int ktice=0; ktice<maxComb; ktice++) {	// pro vsechny k-tice
   	actPrice=0;
    	actWeight=0;
      for (i=0; i<n; i++) actInKnap[i]=false;

		for (i=0; i<constK; i++) {  // pouzit prvky z k-tice
			if (actWeight+V[combinations[i]]<=M) {	// vejde se, dame do batohu
      		actWeight+=V[combinations[i]];
   	  		actPrice+=C[combinations[i]];
   	  		actInKnap[combinations[i]]=true;
			}
		}
      
      NextKtice(n, constK);	// pro priste vygenerujem dalsi k-tici
        
		for (i=0; i<n; i++)	{ // zkusime nastrkat dalsi prvky
			if (actInKnap[i]==false && actWeight+V[i]<=M) {
         	actWeight+=V[i];
				actPrice+=C[i];
				actInKnap[i]=true;
        	}
        	stepNr++;
		}
        	
      if (actWeight<=M && actPrice>knapPrice) {	// nejlepsi reseni?
        	knapPrice=actPrice;
			for (i=0; i<n; i++) 
				inKnap[i]=actInKnap[i];
   	} 
	}
}

//---------------------------------------------------------------------------------

int main(int argc, char *argv[])
{
	char metoda=0;	
  	char str[30];
	char strin[30];

  printf("Knapsack problem 2005 by GS.\n");
  printf("Usage: 4batoh.exe inputfile method\n");
  printf("Output file: price'method'_'inputfile'\n");
  printf("Output step file: step'method'_'inputfile'\n");
  printf("Possible method: [0-4] (default 0)\n");
	printf(" 0- hrubou silou (batoh 1)\n");
	printf(" 1- heurestikou podle pomeru cena/vaha (batoh 1)\n");
	printf(" 2- metoda vetvi a hranic (batoh 2)\n");
	printf(" 3- dynamicke programovani (batoh 2)\n");
	printf(" 4- heurestika vyberem k-tic (batoh 2)\n");
  printf("\n");

  if (argc>2) metoda=atoi(argv[2]);
  if (metoda<0 || metoda>4) metoda=0;
  
  if (argc>1) strcpy(strin,argv[1]);
  else return EXIT_SUCCESS;

	if ((src=fopen(strin,"r"))==NULL) 
	{
		printf(" Error opening %s input file.\n",strin);
		return EXIT_FAILURE;
	}
    sprintf(str,"price%d_%s",metoda,strin);
    if ((dest=fopen(str,"w"))==NULL) {
			printf("Error opening %s output file.\n",str);
      fclose(src);
      return EXIT_FAILURE;
    }
    sprintf(str,"step%d_%s",metoda,strin);
    if ((krok=fopen(str,"w"))==NULL) {
			printf("Error opening %s output file.\n",str);
      fclose(src);
			fclose(dest);
      return EXIT_FAILURE;
    }

  printf("  %d selected. Working.....\n\n",metoda);

    for (int rad=0; rad<50; rad++) {
      knapWeight=0;
      knapPrice=0;
			stepNr=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;
      }
      if (M>maxVaha) {
        printf("Warning: knapsack maxweight overloaded. Using only %d.\n",maxVaha);
        M=maxVaha;
      }
      for (int j=0;j<n;j++) {
		    fscanf(src,"%d ",&V[j]);
        fscanf(src,"%d ",&C[j]);
        inKnap[j]=false;
        nr[j]=j;
      }

			time(&timeStart);
      // timeStart=time(NULL);
			switch (metoda) {
				case 0:
					BruteForce();
					break;
				case 1:
					SortRate();
					Greedy();
					break;
				case 2:
					SortRate();
					Branches(0,M);
					break;
				case 3:
					Dynamic();
					break;
				case 4:
					SortRate();
					HeuresticKtic();
					break;
			}
			time(&timeEnd);
/*
			if (dest) {
				fprintf(dest,"%d %d %d ",id,n,knapPrice);
				if (metoda==1 || metoda==2 || metoda==4) {	// prvky byly setrizeny - dekodovat puvodni posloupnost
					for (int j=0; j<n; j++)
						for (int i=0; i<n; i++)
							if (nr[i]==j) {
								fprintf(dest,"%d ",inKnap[i]);
								break;
							}
				} else
  				for (int i=0; i<n; i++) fprintf(dest,"%d ",inKnap[i]);
				fprintf(dest,"\n");
			}
			*/
			// if (krok) fprintf(krok,"%d %d %d\n",id,stepNr,knapPrice);

			if (krok) fprintf(krok,"%d\n",stepNr);
			fprintf(dest,"%d\n",knapPrice);

    }
    fclose(dest); 
		fclose(src);
		fclose(krok);

	printf("\n  ....................done.\n\n");  
  return EXIT_SUCCESS;
}