Algoritmy
pro řešení problému batohu
(1. úloha)

Na této stránce naleznete moji implementaci použitých algoritmů v C++. Celý zdrojový soubor se nachází zde.

Hrubá síla 1

//pripadne ulozeni vysledku na konci vetve
void _CheckResult()
{
  if (price > result.price)
    SaveData(); //ulozeni aktualni konfigurace do result
}

//zkouseni jednotlivych veci
void _BPTryThing(int index)
{
  //? neni posledni vec
  if (index < result.count)
  {
    //zkusit s veci index
    if ( Add(index) ) {
      _BPTryThing(index + 1);
      Remove(index);
    }
    //zkusit bez
    _BPTryThing(index + 1);
  }
  //za posledni veci - ulozeni vetve
  else
    _CheckResult();
}
 
//hlavni metoda reseni
void BrutalPower()
{
  _BPTryThing(0);
}

Hrubá síla 2

//pole indexu - serazene veci
int *indexes = NULL;

//zkouseni jednotlivych veci
void _BWTryThing(int index)
{
  //? 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;
  //usporadani veci podle vahy - pole indexu
  indexes = WeightSort(result.count);
  _BWTryThing(0);
  delete[] indexes;
  indexes = NULL;
}

Heuristika - poměr cena / váha

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