///////////////////////////////////////////////////////////////
// RESENI HRUBOU SILOU - BrutalPower
// Ciste pouziti hrube sily bez okolnich podminek

	//zkouseni jednotlivych veci
	void _BPTryThing(int index)
	{
		steps++;
		//? neni posledni vec
		if (index < result.count)
		{
			//zkusit s
			if ( Add(index) ) {
				_BPTryThing(index + 1);
				Remove(index);
			}
			//zkusit bez
			_BPTryThing(index + 1);
		}
		//za posledni veci - ulozeni
		else
			CheckResult();
	}
	
	//hlavni metoda reseni
	void BrutalPower()
	{
		steps = 0;
		_BPTryThing(0);
	}
	
	
///////////////////////////////////////////////////////////////
// RESENI HRUBOU SILOU S RAZENIM DLE VAHY
// Veci jsou serazeny od nejlehci - pokud se vec nevejde, nevejde
// se ani zadna po ni

	//zkouseni jednotlivych veci
	void _BWTryThing(int index)
	{
		steps++;
		//? neni posledni vec (pokud se vejdou vsechny)
		if (index < result.count)
		{
			int myindex = indexes[index];
			//? vejde se
			if ( Add(myindex) )
			{
				//zkusit s
				_BWTryThing(index + 1);
				//zkusit bez
				Remove(myindex);
				_BWTryThing(index + 1);
				return;	//kontrola bude dal
			}
		}
		//nevejdu se, tedy nikdo jiny, nebo vsechno pridano - konec
		CheckResult();
	}

	//hlavni metoda reseni
	void BrutalWeight()
	{
		if (indexes != NULL)
			delete[] indexes;
		indexes = WeightSort(result.count);
		steps = 0;
		_BWTryThing(0);
		delete[] indexes;
		indexes = NULL;
	}

	
///////////////////////////////////////////////////////////////
// RESENI HEURISTIKOU DLE POMERU CENA/VAHA
// Veci se usporadaji sestupne dle pomeru cena/vaha a berou
// se, dokud neni batoh plny.

	//hlavni fce metody
	void PriceWeightHeuristic()
	{
		if (indexes != NULL)
			delete[] indexes;
		//usporadani
		indexes = PriceWeightSort(result.count);
		steps = 0;
		//pridavani		
		for (int i = 0; i < result.count; i++)
		{
			steps++;
			if (!	Add(indexes[i]) )
				break;
		}
		SaveData();
		delete[] indexes;
		indexes = NULL;
	}


///////////////////////////////////////////////////////////////
// RESENI HEURISTIKOU CENA/VAHA + NEJTEZSI VEC

	void PriceWeightHeaviest()
	{
		//test heuristikou
		PriceWeightHeuristic();		//nuluje a nacita steps
		//nalezeni nejtezsi veci
		int index = 0;
		int max = things[0].weight;
		for (int i = 1; i < result.count; i++)
		{
			if (things[i].weight > max) {
				index = i;
				max = things[i].weight;
			}
		}
		//test nejtezsi veci
		if (things[index].price > result.price)
		{
			steps++;
			_ClearSack(result.count);	//vysyp batoh
			Add(index);								//pridej nejtezsi
			SaveData();
		}
	}


///////////////////////////////////////////////////////////////
// RESENI MOJI METODOU VETVI A HRANIC
	//maximalni dosazitelne ceny zbylych veci
	int* prices = NULL;
	
	void _VHTryThing(int index)
	{
		steps++;
		//? neni posledni vec (pokud se vejdou vsechny)
		if (index < result.count)
		{
			//? ma cenu pridavat (lze touto vetvi navysit cenu)
			if (price + prices[index] > result.price)
			{
				int myindex = indexes[index];
				//? vejde se - zkusit s
				if ( Add(myindex) )
				{
					//zkusit s
					_VHTryThing(index + 1);
					Remove(myindex);
				}
				_VHTryThing(index + 1);
			}
		}
		//pridany jiz vsechny veci - ulozim stav
		else {
			CheckResult();
		}
	}

	//hlavni funkce metody vetvi&hranic s moznosti volby razeni
	void _VetveHranice(bool priceWeightSort)
	{
		if (indexes != NULL)
			delete[] indexes;
		if (prices != NULL)
			delete[] prices;
		//usporadani
		if (priceWeightSort)
			indexes = PriceWeightSort(result.count);
		else
			indexes = WeightSort2(result.count);
		//ceny
		int price = 0;
		prices = new int[result.count];
		for (int i = result.count - 1; i >= 0; i--)
		{
			price += things[indexes[i]].price;
			prices[i] = price;
		}
		//samotny algoritmus
		steps = 0;
		_VHTryThing(0);
		//uklid
		delete[] prices;
		prices = NULL;
		delete[] indexes;
		indexes = NULL;
	}

	//metoda vetvi a hranic s razenim dle pomeru cena/vaha
	void VetveHranice()
	{
		_VetveHranice(true);
	}



///////////////////////////////////////////////////////////////
// RESENI IDEALNI METODOU VETVI A HRANIC
	//vypocet maximalni dosazitelne ceny pri baleni od index-te veci
	//do batohu s kapacitou capacity - predpoklada razeni dle cena/hmotnost 
	//pridava postupne veci, posledni prida z pomerne casti
	int MaxPrice(int index, int capacity)
	{
		int price = 0;
		int weight;
		//pridani co nejvice celych veci
		while ((index < result.count) && (weight = (things[indexes[index]].weight)) <= capacity)
		{
			capacity -= weight;
			price += things[indexes[index]].price;
			index++;
		}
		//pridani pomerne casti dalsi veci
		if ( (index == result.count) || (capacity == 0) )
			return price;
		else
			return price + (things[indexes[index]].price * capacity) / weight;
	}
	
	//myMaxPrice je maximalni cena dosazitelna aktualni vetvi (celou-od prvni veci)
	void _VH2TryThing(int index, int myMaxPrice)
	{
		steps++;
		//? neni posledni vec (pokud se vejdou vsechny)
		if (index < result.count)
		{
			//? ma cenu pridavat (lze touto vetvi navysit cenu)
			if (myMaxPrice > result.price)
			{
				int myindex = indexes[index];
				//zkusime s - neni treba prepocitavat cenu vetve (postupujeme dle predpokladu)
				if ( Add(myindex) )
				{
					//zkusit s
					_VH2TryThing(index + 1, myMaxPrice);
					Remove(myindex);
				}
				//zkousime bez - nutno prepocist cenu (aktualni + dobaleni zbytku batohu od pristi veci)
				int newPrice = price + MaxPrice(index + 1, remain);
				_VH2TryThing(index + 1, newPrice);
			}
		}
		//pridany jiz vsechny veci - ulozim stav
		else {
			CheckResult();
		}
	}

	//hlavni funkce metody
	void VetveHranice2()
	{
		if (indexes != NULL)
			delete[] indexes;
		//usporadani
		indexes = PriceWeightSort(result.count);
		//samotny algoritmus
		steps = 0;
		_VH2TryThing(0, MaxPrice(0, capacity));
		//uklid
		delete[] indexes;
		indexes = NULL;
	}
	

///////////////////////////////////////////////////////////////
// RESENI DYNAMICKYM PROGRAMOVANIM	
	//pole (count+1) x (capacity+1) spoctenych spoctenych hodnot
	//hodnotou je cena reseni, kladna pokud vec pridana, zaporna jinak
	int *dynData = NULL;
	int length = 0;			//delka radku pole - pocet prvku + 1

	#define EMPTY 999999	//hodnota nevypocteneho prvku

	//vypocet indexu ve 2D poli
	int GetIndex(int count, int capacity)
	{
		return capacity * length + count;
	}

	//forward deklarace
	int DynCompute(int, int);

	//vypocet abs. hodnoty
	int abs(int value)
	{
		return (value < 0) ? -value : value;
	}

	//rozhodnuti o pritomnosti veci po vypoctu - rozhoduje se dle
	//kladne ci zaporne hodnoty v tabulce hodnot
	void DecideThings(int n, int capacity)
	{
		int index = GetIndex(n, capacity);
		int result = dynData[index];
		//? je jeste neco pridano
		if (result != 0)
		{
			//? je vec pridana
			if (result > 0) {
				Add(n - 1);	//pridame vec
				DecideThings(n - 1, capacity - things[n-1].weight);
			}
			//bez pridani
			else
				DecideThings(n - 1, capacity);
		}
	}
	
	//opravdovy vypocet hodnoty - neobsazeno v tabulce
	int ReallyCompute(int n, int capacity)
	{
		steps++;
		//? zadna vec
		if (n == 0)
			return 0;
		//priprava dat
		int index = n - 1;
		int myweight = things[index].weight;
		int without = DynCompute(n - 1, capacity);
		//? vejdu se
		if (myweight <= capacity)
		{
			int with = DynCompute(n - 1, capacity - myweight) + things[index].price;
			//? lepsi pridat
			if (with > without)
			{
				return with;
			}
		}
		//nevejdu se nebo lepsi bez
		return -without;
	}
	
	//rekurzivni vypocet hodnoty pro prvnich n veci s max. kapacitou capacity
	//je testovano obsazeni v tabulce
	int DynCompute(int n, int capacity)
	{
		//vypocet indexu + hodnota v tabulce
		int index = GetIndex(n, capacity);
		int result = dynData[index];
		//? je jiz vypocteno
		if (result != EMPTY)
			return abs(result);
		//neni vypocteno - nutno dopocitat
		return abs(dynData[index] = ReallyCompute(n, capacity));
	}
	
	//reseni dyn. programovanim
	void DynPrograming()
	{
		//alokovani pole na data
		if (dynData != NULL)
			delete[] dynData;
		length = result.count + 1;	//delka radku
		int size = length * (capacity + 1);
		dynData = new int[size];
		//nastaveni pole na "nepocitano"
		for (int i = 0; i < size; i++)
			dynData[i] = EMPTY;
		//spusteni vypoctu
		steps = 0;
		DynCompute(result.count, capacity);
		//naplneni batohu dle vysledku
		DecideThings(result.count, capacity);
		//ulozeni vysledku + uklid
		SaveData();
		delete[] dynData;
		dynData = NULL;
	}

///////////////////////////////////////////////////////////////
// ME RADICI FUNKCE (QuickSort by byl lepsi, ale kdo toma vymejslet)

	//serazeni veci VZESTUPNE dle vahy -------------------
	// vraci pointr na pole indexu
	int* WeightSort(int count)
	{
		int *array = new int[count];
		//vyplneni pole postupnymi indexy
		for (int in = 0; in < count; in++)
			array[in] = in;
		//serazeni
		for (int i = 0; i < count - 1; i++)
		{
			int
				minIndex = i,
				min = things[array[i]].weight;
			//nalezeni minima
			for (int j = i + 1; j < count; j++)
			{
				if (things[array[j]].weight < min)
				{
					min = things[array[j]].weight;
					minIndex = j;
				}
			}
			//ulozeni minima
			int pom = array[i];
			array[i] = array[minIndex];
			array[minIndex] = pom;
		}
		return array;
	}
	
	//serazeni veci SESTUPNE dle vahy -----------------------------
	// vraci pointr na pole indexu
	int* WeightSort2(int count)
	{
		int *array = new int[count];
		//vyplneni pole postupnymi indexy
		for (int in = 0; in < count; in++)
			array[in] = in;
		//serazeni
		for (int i = 0; i < count - 1; i++)
		{
			int
				maxIndex = i,
				max = things[array[i]].weight;
			//nalezeni minima
			for (int j = i + 1; j < count; j++)
			{
				if (things[array[j]].weight > max)
				{
					max = things[array[j]].weight;
					maxIndex = j;
				}
			}
			//ulozeni minima
			int pom = array[i];
			array[i] = array[maxIndex];
			array[maxIndex] = pom;
		}
		return array;
	}
	
	//serazeni dle pomeru cena/vaha -----------------------------------
	int* PriceWeightSort(int count)
	{
		int *array = new int[count];
		double *key = new double[count];
		int i;
		//iniciace poli
		for (i = 0; i < count; i++)
		{
			array[i] = i;
			key[i] = (double)things[i].price / things[i].weight;
		}
		//razeni
		for (i = 0; i < count - 1; i++)
		{
			int maxIndex = i;
			double max = key[array[i]];
			//nalezeni maxima
			for (int j = i + 1; j < count; j++)
			{
				if (key[array[j]] > max)
				{
					max = key[array[j]];
					maxIndex = j;
				}
			}
			//ulozeni minima
			int pom = array[i];
			array[i] = array[maxIndex];
			array[maxIndex] = pom;
		} //for i
		delete[] key;
		return array;
	}