algo:knapsack

Diskussionen zu Tutorials, Änderungs- und Erweiterungswünsche
haiko
Beiträge: 2
Registriert: Sa Sep 25, 2021 9:51 am

algo:knapsack

Beitrag von haiko » Sa Sep 25, 2021 9:56 am

Hallo Autor,

danke für den sehr guten und anschaulich geschriebenen Artikel.

Leider basiert die verbesserte Optimierung in der dynamischen Variante darauf, daß das Volumen immer ganzzahlig ist
und die Anzahl der Iterationen wird durch die Anzahl der "buckets" (freie Volumina) bestimmt.
Bei Volumen die nicht ganzzahlig sind (oder sehr groß) sind sieht die Sache aber anders aus. An der Stelle kann auf vorberechnete
freie Volumina nicht mehr zurückgegriffen werden. Da kann man nur noch mit Rekursion arbeiten. Die Rekursion ist problematisch
in zweierlei Hinsicht: die Anzahl der Rekursionen verdoppelt sich mit jedem weiteren Element, und der Status kann nicht ohne
Weiteres gespeichert werden. Also z.B. alle Varianten mit gleichem Füllstand oder Füllgewicht.

Ich bin ein großer Anhänger davon rekursive Probleme zu linearisieren, sodaß sich solche Problemstellungen in einem einzigen
linearen Durchlauf abhandeln lassen. Das hat den Vorteil, daß es keine rekursiven Funktionsaufrufe gibt die den Stack belasten
oder unnötigen zusätzlichen Speicherverbrauch zur Folge haben. Im obigen Beispiel bedeutet das, daß nicht ganzzahlige Werte in
Pseudo-"buckets" umgewandelt werden müßten. Je nach Genauigkeit kann die Matrix dann schon sehr groß werden.

Mein Ansatz das Problem zu vereinfachen ist ein Enumerator der alle Varianten "abzählt". Das erscheint im ersten Moment unsinnig
weil für jeden Zustand das Volumen und das Gewicht errechnet werden müssen.

Die Lösung liegt in einem Enumerator der alle Varianten abdeckt aber die die Anzahl der Operationen auf ein Minimum reduziert.
Die Lösung ist ein "Gray-Code"-Enumerator! Wie bekannt ist ändert sich dort immer nur ein Bit (im Zustandsfeld [bitfield]; Gegenstand
ist drin oder draußen) und bedeutet also immer nur eine Operation pro Aufzählungsschritt.

Der Enumerator liefert immer nur die Werte "Bitposition" (Index des Elements) und ob das Bit gesetzt oder zurückgesetzt wird.
In der Folge müssen nun zum Volumen und Gewicht immer nur die Werte für das jeweilige Element (Bitposition) addiert oder subtrahiert
werden. So werden wirklich alle Varianten ermittelt, im Gegensatz zur Rekursion die bei "Rucksack ist voll" abbricht.

Dies hat folgende Vorteile: es können mehrere Zustände ausgewertet werden, der Zustand kann jederzeit gespeichert werden (das Bitfeld),
der Algorithmus ist nur geringfügig langsamer, es ist kein zusätzlicher Speicher notwendig, keine rekursiven Funktionsaufrufe. Alle
Operationen spielen sich in einer einzigen linearen Schleife ab. Abbruchkriterium ist die Anzahl der Elemente.

Es können also z.B. verschiedene "Rucksäcke" optimiert werden. Oder der optimale Füllzustand mit dem höchsten Gewicht ermittelt werden.
Wie gesagt alle diese Möglichkeiten sind möglich mit nur einer geringfügig höheren Laufzeit (als Rekursion, die ja bei "voll" abbricht).

Natürlich ist die Anzahl der Iterationen genau wie die Rekursion stark von der Anzahl der Elemente abhängig (ein Element mehr bedeutet
doppelte Laufzeit; O(2^n) ). Der Algorithmus ist also nur für maximal ca. 30-34 Elemente in akzeptabler Zeit sinnvoll. Kann man mit
diesen Einschränkungen leben, lassen sich viele verschiedene Szenarien damit realisieren.

Mit freundlichen Grüßen.

Code: Alles auswählen

--- CEnumGrey64.h ---

class CEnumGrey64 : public vEnumerator
{
public:
	CEnumGrey64(const unsigned int bitcount,const unsigned __int64 init=0);

	virtual int						Next(unsigned int& bit,int& add);
	virtual void					Save(BITBUFF& buff);
	virtual const TCHAR*	toString(tArr<TCHAR>& buff);
	virtual const TCHAR*	toString(const unsigned int* bits,tArr<TCHAR>& buff);

private:
	unsigned int*					lp(){ return (unsigned int*)&_curr; }

	const unsigned int	_bitcount;
	unsigned __int64		_counter;
	unsigned __int64		_curr;
	unsigned __int64		_prev;

};

------------------------------------------------------------
--- CEnumGrey64.cpp ---

CEnumGrey64::CEnumGrey64(const unsigned int bitcount,const unsigned __int64 init):_bitcount(bitcount)
{
	_counter = init;
	_curr    = 
	_prev    = init ^ (init>>1);
}

int CEnumGrey64::Next(unsigned int& bit,int& add)
{
	unsigned long	bb;

	++_counter;
	_prev = _curr;
	_curr = _counter ^ (_counter>>1);

	if( _BitScanReverse64(&bb,_prev^_curr) )
	{
		bit = bb;
		add = _curr & ((const unsigned __int64)1<<bb)?true:false;
		return bit<_bitcount;
	}

	return false;
}

void CEnumGrey64::Save(BITBUFF& buff)
{
	buff.resize(2);
	buff.array[0] = lp()[0];
	buff.array[1] = lp()[1];
}

const TCHAR* CEnumGrey64::toString(tArr<TCHAR>& buff)
{
	return toString(lp(),buff);
}

const TCHAR* CEnumGrey64::toString(const unsigned int* bits,tArr<TCHAR>& buff)
{
	unsigned int	ix;
	unsigned int	index = 0;
	unsigned int	bit   = 1;
	buff.resize(_bitcount+1);
	for(ix=_bitcount;0<ix;)
	{
		--ix;
		buff.array[ix] = bit & bits[index]?'1':'0';
		bit <<= 1;
		if(!bit){ ++index; bit = 1; }
	}
	buff.array[_bitcount] = 0;
	return buff.array;
}

------------------------------------------------------------
--- main.cpp ---

#include "initial.h" // <= __w[] /*Gewichte*/ <= __v[] /*Volumina*/

typedef int		MEASURE; /* double wenn __w und __v vom typ double sind */

int _tmain(int argc, _TCHAR* argv[])
{
	enum{ ELEMENT_COUNT = sizeof(__w)/sizeof(__w[0]), };
	CHiTime				time;

	CEnumGrey64		enu(ELEMENT_COUNT);

	unsigned int	bit;
	int						add;
	tArr<TCHAR>		buf;

	MEASURE				sumV = 0; // <= aktuelles Volumen
	MEASURE				sumW = 0; // <= aktuelles Gewicht
	MEASURE				mayV0 = 0;
	MEASURE				mayW0 = 0;
	MEASURE				mayV1 = 0;
	MEASURE				mayW1 = 0;

	tArr<unsigned int>	saved0;
	tArr<unsigned int>	saved1;

	unsigned int				steps = 0; // Anzahl der Iterationen

	while( enu.Next(bit,add) )
	{
		++steps;
		// berechnen
		if(add){ sumV += __v[bit]; sumW += __w[bit]; }else{ sumV -= __v[bit]; sumW -= __w[bit]; }

		// auswerten
		if( sumV<=_max_V )
		{
			if(sumW>mayW0) // maximales Gewicht
			{
				mayW0 = sumW; mayV0 = sumV;
				enu.Save(saved0);
			}
			if(sumV>mayV1) // maximaler Füllgrad+Gewicht
			{
				mayW1 = sumW; mayV1 = sumV;
				enu.Save(saved1);
			}
			else if((sumV==mayV1)&&(sumW>mayW1))
			{
				mayW1 = sumW; mayV1 = sumV;
				enu.Save(saved1);
			}
		}
	}
	
	// Ergebnis anzeigen
	if(0<mayW0) _tprintf(__T("[max:%lf:%lf] %s\r\n"),(double)mayW0,(double)mayV0,enu.toString(saved0.array,buf));
	if(0<mayW1) _tprintf(__T("[max:%lf:%lf] %s\r\n"),(double)mayW1,(double)mayV1,enu.toString(saved1.array,buf));

	_tprintf(__T("<key>[%u] %d ms"),steps,time.GoneIms()); _gettch();
	return 0;
}
EDIT nufan: Code-Tags

nufan
Wiki-Moderator
Beiträge: 2557
Registriert: Sa Jul 05, 2008 3:21 pm

Re: algo:knapsack

Beitrag von nufan » Mo Sep 27, 2021 8:38 am

Hallo haiko! Autor hier ;)

Du hast natürlich vollkommen recht, die im Wiki präsentierte Lösung geht von Ganzzahlen aus. Hast du vielleicht Interesse daran, deine Lösung in den Wiki-Artikel zu integrieren?

haiko
Beiträge: 2
Registriert: Sa Sep 25, 2021 9:51 am

Re: algo:knapsack

Beitrag von haiko » Di Sep 28, 2021 11:58 am

Ja gern. Dafür bräuchte ich jedoch eine kleine Anleitung.
Mit freundlichen Grüßen auch für die prompte Antwort.

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8858
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: algo:knapsack

Beitrag von Xin » Do Sep 30, 2021 3:19 pm

Anleitung welcher Art?

Du brauchst einen Wiki-Account. Ansonsten schick ich Dir mal eine PN für weiteres. :-)
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

nufan
Wiki-Moderator
Beiträge: 2557
Registriert: Sa Jul 05, 2008 3:21 pm

Re: algo:knapsack

Beitrag von nufan » Fr Okt 01, 2021 8:16 am

haiko hat geschrieben:
Di Sep 28, 2021 11:58 am
Ja gern. Dafür bräuchte ich jedoch eine kleine Anleitung.
Ich würde vorschlagen du erstellst eine neue Seite in deinem Benutzer-Namespace, z.B. hier:
https://www.proggen.org/doku.php?id=haiko:knapsack
Dort kannst du dich gerne austoben und dich mit der Wiki-Software vertraut machen :)

Wir können dann https://www.proggen.org/doku.php?id=haiko:knapsack neu strukturieren und auf mehrere Seiten aufteilen.

Antworten