Knapsack problém – C / C++ – Fórum – Programujte.com
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu

Knapsack problém – C / C++ – Fórum – Programujte.comKnapsack problém – C / C++ – Fórum – Programujte.com

 

Gadael0
Návštěvník
1. 2. 2011   #1
-
0
-

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.–
Nejhorsi, co se Vam v zivote muze prihodit je, ze narazite na blbce...
Gadael0
Návštěvník
2. 2. 2011   #2
-
0
-

Vážně nikdo nevíte? Potřeboval bych s tímhle poradit.

Dík moc.

Nahlásit jako SPAM
IP: 212.24.139.–
Nejhorsi, co se Vam v zivote muze prihodit je, ze narazite na blbce...
Zjistit počet nových příspěvků

Přidej příspěvek

Toto téma je starší jak čtvrt roku – přidej svůj příspěvek jen tehdy, máš-li k tématu opravdu co říct!

Ano, opravdu chci reagovat → zobrazí formulář pro přidání příspěvku

×Vložení zdrojáku

×Vložení obrázku

Vložit URL obrázku Vybrat obrázek na disku
Vlož URL adresu obrázku:
Klikni a vyber obrázek z počítače:

×Vložení videa

Aktuálně jsou podporována videa ze serverů YouTube, Vimeo a Dailymotion.
×
 
Podporujeme Gravatara.
Zadej URL adresu Avatara (40 x 40 px) nebo emailovou adresu pro použití Gravatara.
Email nikam neukládáme, po získání Gravatara je zahozen.
-
Pravidla pro psaní příspěvků, používej diakritiku. ENTER pro nový odstavec, SHIFT + ENTER pro nový řádek.
Sledovat nové příspěvky (pouze pro přihlášené)
Sleduj vlákno a v případě přidání nového příspěvku o tom budeš vědět mezi prvními.
Reaguješ na příspěvek:

Uživatelé prohlížející si toto vlákno

Uživatelé on-line: 0 registrovaných, 19 hostů

Podobná vlákna

Problém v C — založil Robin

Problem — založil Ghosta

Problém — založil Ma.ty

Problém — založil pali6

Problem — založil roonill

Moderátoři diskuze

 

Hostujeme u Českého hostingu       ISSN 1801-1586       ⇡ Nahoru Webtea.cz logo © 20032024 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý