Greedy-Strategie < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 18:29 So 09.05.2010 | | Autor: | matheja |
| Aufgabe | Schönen Sonntag alle, 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: [mm] v_i/w_i [/mm] i [mm] \in [/mm] {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.
beste grüße vom matheja
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 07:20 Mi 12.05.2010 | | Autor: | felixf |
Moin!
> Schönen Sonntag alle, 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 ?
Exakt.
> b)Greed Strategie:
>
> 1) Greedy-Strategie:
>
> Berechne Wert/ Gewicht für alle Gegenstände: [mm]v_i/w_i[/mm] i
> [mm]\in[/mm] {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
![[ok]](/images/smileys/ok.gif "[ok]")
> 2.Greedy-Strategie:
> mir fällt keine weitere strategie ein?
> wie kann man noch vorgehen
Such dir doch unter den Gegenstaenden, die noch reinpassen, den mit dem groessten Wert aus (und nicht mit dem groessten Quotient aus Wert und Gewicht).
> c)
>
> auch hier brauch ich hilfe.
Finde (jeweils) ein Zahlenbeispiel, wo sie nicht optimal sind. Bei der ersten Strategie hast du ja schon eins.
LG Felix
|
|
|
|
