TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
Návštěvník
Zdravím, zkouším si dělat v c++ knapsack problém (http://en.wikipedia.org/wiki/Knapsack_problem), zatím hrubou silou.
T.j. potřebuju projít všechny možné kombinace věcí a zkoušet jestli součet cen je maximální a stále se ještě do batohu vejdou.
Zatím jsem si vytvořil 'strukturu prostředí' - třídu batoh:
class Knapsack {
public:
vector<Item> items;
int capacity;
int numb;
int ID;
Knapsack();
Knapsack(int c, int n, int ident, vector<Item> *things);
};V tom vektoru items mám jednotlivé objekty představující věci, které budu vkládat do batohu.
Tak a teď začínám vytvářet samotný algoritmus a hned jsem se zaseknul na tom, že mě nenapadá, jakým způsobem projít všechny kombinace.. Ten cyklus bude vypadat nejak takhle:
for(int i=0; i<pow(2,numb);i++)protože potřebuju projít 2^n kombinací, jak ale bude aspon v pseudokodu vypadat tělo toho cyklu? Jakým způsobem zkoušet ty kombinace?
Díky moc,
H.
Nahlásit jako SPAM
IP: 193.165.2.–
Zjistit počet nových příspěvků
