Unabhängigkeitssystem, Rucksackproblem und Greedy

Neue Frage »

Nena678 Auf diesen Beitrag antworten »
Unabhängigkeitssystem, Rucksackproblem und Greedy
Meine Frage:
Hallo,

der Einfachheitshalber hab ich die Aufgabe als Bild angehängt.

Nach ein bisschen im Internet forschen hab ich raus gefunden dass es verschiedene
Knapsackprobleme (Rucksackprobleme) gibt. Nämlich 0-1 und etwas anderes, aber hier
gehts nur um das 0-1 Problem also immer das Gewicht und nicht nur einen Teil des Gewichtes.

Def. Maximierungsproblem
Ein Max.prob. über einem US U=(E,I) ist gegeben durch eine Gewichtsfunktion
und die Aufgabe: Finde A* in I sodass
mit c(A*) = max c(A). (also A* so groß wie möglich mit A* in I)




Meine Ideen:
a)


Also Grundsätzlich würde ich mal einen Graphen G aufstellen, bei dem ich
als Knoten nehme und jeden mit jedem Verbinde.
Also G=(V,E) vollständiger Graph. Was irgendwie ja auch sinvoll ist, da ich nach jedem
Gegenstand der in den Rucksack kommt jeden beliebigen als nächstes nehmen kann.

Das t brauche ich dafür das falls beim Algorithmus in b) alle G in den Rucksack passen
und ich dann einen Kreis hätte was nicht mehr in I liegen würde.

Anschließend würde ich mein Unabhängigkeitssystem(US) wie folgt aufstellen:
mit E Kantenmenge von G und
Damit ist nach Vorlesung U ein Matroid und somit ein US.

Nun muss ich unter maximieren unter der Berücksichtigung der Gewichte. Damit habe ich ein Maxiemierungsproblem.



b)


,
wobei der Wert von und ,
R ... max. Rucksackgewicht

___________________________________________________________________________
_____

Input: , ,, R
Output:



BEGIN
sortiere E*, sodass


<-
b <- 0
B <-

FOR i=1 to n DO
(b <- b +
B <-

IF b>R DO
b <- b -
B <- B\
)

k <- |B|

FOR i=1 to k-1 DO
( <-
)

<-

END

___________________________________________________________________________
___________

dabei sind die Kanten die Kante von nach und die Letzte Kante ist immer zu t




C)

unter Rang, oberer Rang und Rangquotient alle 1 da U Monoid (wurde in VL gezeigt)


d)
Da weiß ich nicht genau was ich machen soll das ja jedes Beispiel das Minimum des Rangquotienten erreicht (hab ich voher etwas falsch gemacht?) genau so weiß ich nicht wirklich etwas mit dem wort Performance anzufangen
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »