Greedy-Strategie

[medicus]

ich lern grad ein bisschen und brauch bei einer Aufgabe aber Hilfe.

Die Besatzung eines Raumschiffs findet auf einem entfernten Planeten folgende 3 Gegenstände:
Gegenstand Gewicht (in kg) Wert
1 10 60
2 20 100
3 30 120

Man möchte Gegenstände somitnehmen, dass der Profit möglichst hoch ist. Das Raumschiff kann aber nur noch 50 kg transportieren, so dass man nicht alle 3 Gegenstände mitnehmen kann, sondern höchstens 2 davon.

a) Was ist die optimale Lösung des obigen Problems?

b) Entwickeln Sie 2 mögliche Greedy-Strategien für dieses Problem.

c) Sind diese Strategien immer optimal ? Begründen Sie Ihre Antwort

Defintion Greedystrategie:

Der Greedy-Ansatz verwendet die Strategie
Top-down Auswahl: Bestimme in jedem Schritt eine lokal
optimale Lösung, so dass man eine global optimale Lösung erhält.

a) Ich seh drei Möglichkeiten:
i): 1+2 => Gewicht:30 und Wert:160
ii): 1+3=> Gewicht:40 und Wert:180
iii):2+3=> Gewicht:50 und Wert:220

iii): Erscheint als optimale Lösung des Problems , weil hier der Wert also der Profit am größten ist oder ?


b)Greed Strategie:

1) Greedy-Strategie:

Berechne Wert/ Gewicht für alle Gegenstände: $ v_i/w_i $ i $ \in $ {1,2,3}

Gegenstand 1: 6
Gegenstand 2: 5
Gegenstand 3: 4

Fülle Raumschiff mit den Gegenständen beginnend mit den höchsten wert bis Rucksack voll ist
6+5 Value => Greedy Lsg:10+20= 30 Kg und Wert :160


2.Greedy-Strategie:
mir fällt keine weitere strategie ein?
wie kann man noch vorgehen

c)

auch hier brauch ich hilfe.




LG

medicus

 

[SlaterB]

zweite Möglichkeit: als erstes den teuersten Gegenstand einpacken wenn er gewichtsmäßig passt, danach den nächsten usw.
ist was anderes als nach Wert/ Gewicht, weiß nicht ob das der Greedy-Definition widerspricht?

c)
dass deine Strategie b)1) falsch bzw. nicht optimal ist, zeigt ja schon die Beschreibung in deiner Antwort,
meine zweite Möglichkeit wäre hier optimal, aber da findet sich doch auch eine Gegenkonstellation

Beispiele sind immer ideal um etwas zu widerlegen

 

[Marco13]

b) Man könnte eine NOCH einfachere verwenden, z.B. immer den Gegenstand mit dem höchsten Wert nehmen, der noch reinpasst. Dein Vorschlag wirkt da fast noch "ausgefeilter", könnte also ggf. als zweiter genannt werden.

c) Die Antwort ist "Nein", weil (Metabegründung: ) sonst P=NP gelten würde. Die Begründung ist ganz einfach: Finde ein Beispiel, wo diese Strategien NICHT die optimale Lösung finden

 

[Landei]

Gegenbeispiel ist ganz einfach: 10 kg maximal erlaubt, drei Teile:
1) 5kg 5EUR (1EUR/kg)
2) 5kg 5EUR (1EUR/kg)
3) 6kg 9EUR (1.5EUR/kg)
Beide Greedy-Verfahren (absolut Teuerstes zuerst, Teuerstes pro Gewichtseinheit zuerst) würden hier als Lösung 3) mit 9EUR ausspucken, wärend der Maximalwert 1) + 2) mit 10EUR wäre.