 Dynamische Programmierung - Teilsummenproblem? |
Charmebinder
unregistriert
 |
|
| Dynamische Programmierung - Teilsummenproblem? |
     |
Hallo zusammen,
stehe vor folgendem Problem, welches mittels dynamischer Programmierung zu lösen ist:
Eine Reederei hat n Schiffe F_1, ..., F_n wobei das j-te Schiff Kapazität k_j und Betriebskosten (also falls tatsächlich unterwegs) b_j hat.
Es sollen m Container - alle mit der gleichen Größe K - transportiert werden, dabei sind die Betriebskosten zu minimieren.
o.B.d.A. seien Kapazität und Betriebskosten natürliche Zahlen und ich kann mit n Schiffen tatsächlich alle m Container transportieren.
Bezeichne S_i,j die minimalen Betriebskosten, um i Container mit den Schiffen F_1,....,F_j zu transportieren.
Wie kann ich S_i,j rekursiv formulieren (die Basisfälle i=0 oder j=0 haben S_i,j = 0 als Lösung),
um dann daraus einen Algorithmus nach dynamischer Programmierung zu formulieren?
Ich kann daraus ein Teilsummenproblem - wie z.B. das Rucksackproblem basteln, indem ich nicht verlange, dass die summierten Kapazitäten mindestens i*K betragen (bei i Containern), sondern die negativen summierten Kapazitäten maximal i*K.
und anstatt die summierten Betriebskosten zu minimieren, summiere ich die negativen Betriebskosten und will die nun maximieren.
Allerdings kann ich die Rekursion des Rucksackproblems nicht auf mein modifiziertes Problem anpassen und das ist das einzige Teilsummenproblem das ich kenne.
Hoffe, ihr könnt mir helfen.
Danke.
|
|
12.07.2017 13:54 |
|
|
Gast
unregistriert
|
|
| RE: Dynamische Programmierung - Teilsummenproblem? |
|
Ich denke, Dein Problem entspricht genau dem Rucksackproblem.
Dazu musst Du die Frage nur mal andersrum formulieren: Wie viele Container können maximal transportiert werden, wenn die Betriebskosten höchstens B sein dürfen?
Nimm dann für die Rekursionsgleichung S_ij = max. Containeranzahl bei Betriebskosten i mit den Schiffen F_1 bis F_j - das sollte dann genau wie beim Rucksackproblem berechnet werden können.
Der dynamische Programmierungsalgorithmus berechnet dann die Tabelle S_ij iterativ für wachsende i und j - er kann aufhören, wenn erstmals die geforderte Kapazität K erreicht wird.
|
|
|
16.07.2017 01:24 |
|
|
|
