Snížení složitosti algoritmu – C / C++ – Fórum – Programujte.com
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
Reklama
Reklama

Snížení složitosti algoritmu – C / C++ – Fórum – Programujte.comSnížení složitosti algoritmu – C / C++ – Fórum – Programujte.com

 

Hledá se programátor! Plat 1 800 € + bonusy (firma Boxmol.com)
Gadael0
Návštěvník
6. 2. 2011   #1
-
0
-

Zdravím,

napsal jsem program, který implementuje problém batohu (mám n věcí, které mají své ceny a snažím se dostat do batohu s kapacitou M co nejvíce věcí aby celková cena byla maximální).

Tady je funkce, která zajišťuje kalkulaci hrubou sílou (zkouším veškeré kombinace věcí):

void Knapsack::Calculate(ofstream& fout, int ID, int n, int M, vector<Item>& items){

int max_cost = -1;
int mask, totalweight, totalprize;
bool overloaded;
vector<bool> max_things;
unsigned int iterations = (int)pow(2.0f, n);

for(int i = 1; i < iterations; i++)
{
vector<bool> things;
totalweight = 0;
totalprize = 0;
overloaded = false;
mask = 1;

for(int j = 0; j < n; j++)
{
things.push_back(i & mask);
totalweight += items[j].weight * things[j];
totalprize += items[j].cost * things[j];
if(totalweight > M)
{
overloaded = true;
break;
}
mask <<= 1;
}

if(!overloaded && totalprize > max_cost)
{
reverse(things.begin(), things.end());
max_cost = totalprize;
max_things = things;
}
}
fout << ID << " " << n << " " << max_cost << " ";
vector<bool>::const_iterator it;
for(it = max_things.begin(); it != max_things.end(); it++)
fout << " " << *it;
fout << endl;
}


Ten vnější cyklus představuje projítí všech kombinací, kterých je 2^n. Tzn. minimální (a očekávaná) složitost je 2^n. Uvnitř mám další for cyklus, který proběhne v nejhorším případě n-krát (kontroluju, jestli už jsem nepřekročil kapacitu). V něm sestavuju binární podobu kombinace věcí a sčítám jejich hmotnosti a ceny.

Nedá se to udělat nějak aby celková složitost bylo pouze těch 2^n, prostě to nějak zrychlit?

Dik moc,
H.

Nahlásit jako SPAM
IP: 193.165.2.–
Nejhorsi, co se Vam v zivote muze prihodit je, ze narazite na blbce...
Reklama
Reklama
nervak0
Věrný člen
6. 2. 2011   #2
-
0
-

Při každém průchodu se vytváří, plní a ruší vektor. V případě vhodnější kombinace se ještě reversuje a kopíruje. Všechno zbytečně. To násobení taky nepotřebuješ. Bez těch zbytečností by to mělo být výrazně rychlejší.

for (int j = 0; j < n; j++)

{
if (i & mask)
{
totalweight += items[j].weight;
totalprize += items[j].cost;
if (totalweight > M)
{
overloaded = true;
break;
}
}
mask <<= 1;
}

if (!overloaded && totalprize > max_cost)
{
max_cost = totalprize;
max_i = i;
}
A snadno můžeš přeskočit spoustu kombinací, u kterých víš, že taky nebudou vyhovovat.

Nahlásit jako SPAM
IP: 213.211.51.–
Gadael0
Návštěvník
6. 2. 2011   #3
-
0
-

Díky za pomoc. Takže chápu to dobře, že výsledkem tohoto je to 'i', což je dekadické číslo představující optimální kombinaci věcí?

To je super rešení, teď se akorát snažím vymyslet, jakým způsobem a co 'nejlevneji' vypsat tu kombinaci binárně. Tzn. pro i=4 potřebuju vypsat 0100, i=11 potřebuju 1011, atd;

Nahlásit jako SPAM
IP: 212.24.139.–
Nejhorsi, co se Vam v zivote muze prihodit je, ze narazite na blbce...
nervak0
Věrný člen
6. 2. 2011   #4
-
0
-

To můžeš klidně udělat tím vektorem, mimo ten cyklus už na rychlosti tolik nesejde.

Nahlásit jako SPAM
IP: 213.211.51.–
nervak0
Věrný člen
6. 2. 2011   #5
-
0
-

To můžeš klidně udělat tím vektorem, mimo ten cyklus už na rychlosti tolik nesejde.

Nahlásit jako SPAM
IP: 213.211.51.–
Franceq+1
Stálý člen
6. 2. 2011   #6
-
0
-

jednoduchy xD vemes cislo a delis ho 2 modulem (se zbytkem) a vysledek zapisujes z prava doleva .....priklad
10
10 % 2 = 0 nulu zapisu na konec...... 0
10 = 10 / 2 =5 timto udelam z desitky 5
5%2 = 1 jednicku zapisu vedle nuly takze to bude vypada takhle 10
5 = 5/2 = 2 tak takhle zas zmensim 5 o polovinu (celociselne)
2%2 = 0 takze mam 010
2/2 = 1
1%2 = 1 takze 1010 juhuu to jsem chtel....a mas to a ted uz jen pro poradek 1/2 = 0
a kdyz chces jinou soustavu treba 3jkovou...nKovou tak misto 2jky pouzijes co chces 3,...n....._)

nebo si nemel tohle na mysli?? necetl jsem si to predtim xD bylo to moc dlouhy...:-)

Nahlásit jako SPAM
IP: 213.235.145.–
Gadael0
Návštěvník
6. 2. 2011   #7
-
0
-

Udělal jsem to pomocí toho bool vektoru a šlape to. Takže díky.

Jenom pro zajímavost - pro 20 věcí (1048576 kombinací) to teď počítá 3 minuty.

Nahlásit jako SPAM
IP: 212.24.139.–
Nejhorsi, co se Vam v zivote muze prihodit je, ze narazite na blbce...
nervak0
Věrný člen
6. 2. 2011   #8
-
0
-

To je nějak moc, na čem to spouštíš a jak dlouho to trvalo předtím?

Nahlásit jako SPAM
IP: 213.211.51.–
Gadael0
Návštěvník
6. 2. 2011   #9
-
0
-

Předtím to nemělo pro n=20 vůbec cenu zkoušet. Zapoměl jsem říct, že to zkouším na 'sadě' 50ti batohů (stejná kapacita i počet věcí, ale různé hmotnosti i ceny). Takže na jednu sadu to vychází asi 3,5 vteřiny.

Jinak Intel Core2 Duo 2GHz, Windows 7.

Nahlásit jako SPAM
IP: 212.24.139.–
Nejhorsi, co se Vam v zivote muze prihodit je, ze narazite na blbce...
nervak0
Věrný člen
6. 2. 2011   #10
-
0
-

Jo, 3.5 s. už vypadá líp.

Nahlásit jako SPAM
IP: 213.211.51.–
nervak0
Věrný člen
6. 2. 2011   #11
-
0
-

Jo, 3.5 s. už vypadá líp.

Nahlásit jako SPAM
IP: 213.211.51.–
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, 165 hostů

Podobná vlákna

Snížení svitu led — založil Prochis

Zjednodužšení algoritmu — založil tomas.ch

Visualizace algoritmu — založil Gadael

Moderátoři diskuze

 

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