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

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;

}

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;

}

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;

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

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

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...:-)

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.

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

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.

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

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