Rucksack Problem

[blubbiblubb]

Hallo.

Aufgabe:
In der Vorlesung wurde ein Algorithmus vorgestellt, der das Rucksackproblem löst. Genauer löst der
vorgestellte Algorithmus allerdings nur die Optimierungsversion, da lediglich der Profit einer optimalen
Packung berechnet wird, aber keine Menge von Gegenständen mit diesem optimalen Profit. Erweitern
Sie den Algorithmus derart, dass nicht nur der optimale Profit, sondern auch eine dazu passende Auswahl
von Gegenständen ermittelt wird. Implementieren Sie den erweiterten Algorithmus und testen Sie ihn mit
geeigneten Beispielen.

int P[] = new int[n];
int w[] = new int[n];
//Eingabe...
...
//Alg:
int s = 0;
for(int i = 0;i <= n-1; i++)
  s = s + P[i];
  //Initialisieren, A[0][.]
  int A[][] = new int[n][s+1];
  for(int t = 0;t <= s; t++){
    if (P[0] != t)
      A[0][t] = B + 1;
    else
      A[0][t] = w[0];
  }
  A[0][0] = 0;
  //Berechnung der Werte A[1][.], A[2][.],...,A[n-1][.]
  for(int t = 0;t <= s; t++){
    if (t < P[i])
      A[i][t] = A[i-1][t];
    else if (A[i-1][t] <= A[i-1][t-P[i]] + w[i])
       A[i][t] = A[i-1][t];
    else
      A[i][t] = A[i-1][t-P[i]] + w[i];
    }
  }
//Bestimme max j mit A[ne-1][j]  B
int j = 0;
for(int t = 1;t <= s; t++){
  if (A[n-1][t] <= B){
    j = t;
  }
}

Ich habe leider keine Idee, wie ich das Umsetzen kann und hoffe, dass ihr mir vielleicht ein wenig dabei helfen könntet.

 

[KSG9|sebastian]

haha das ist ja wohl ein scherz, oder ?
Wir lösen hier keine Hausaufgaben. Zum Code:

Ihr hättet doch alle Variablen i, ii, iii, iiii, iiiii u.s.w. nennen könne, dann wäre es noch unübersichtlicher geworden als es schon ist.
Die Kommentare im Code...hm...ja...mehr oder weniger sinnlos. Das "j" berechnet wird oder a[j] bis a[..] seh ich ja, aber WAS soll in diesen i, j, k, p, a,-Variablen drinstehen ?

Und noch was: Rucksackproblem ?
Ich kann mir zwar ungefähr vorstellen was du meinen könntest, aber 1. wird es durch den code nicht ersichtlich 2. hab ich die Glaskugel verloren

Erkär doch mal das Codestück und wo du nicht weiterkommst. Aber bitte keine "ich komm gar nicht weiter"-Antwort, sonst schließ ich das Thema.

Gruß

Edit:

Wenn du uns ein konkretes Problem stellst sind wir natürlich auch bereit dir zu helfen. Sofern wir ne Lösung kennen. Aber auf "Hier ist die Aufgabe - gebt mir ne Lösung" reagieren wir nicht wirklich fröhlich, wie du siehst.

 

[blubbiblubb]

Du hast ja selbst gesagt, dass man den Code nicht versteht, da fängt das Problem ja schon mal an, wie soll ich etwas lösen können, wenn mir der Code nicht mal klar ist.

Und falls du dich dann besser fühlst, dann schliesse einfach den Tread, wenn du meinst das es gut ist so miteinander umzugehen!

Schöne Grüsse,

mich wirst du hier jedenfalls nicht mehr sehen

(PS.: Ein Kommentar deinerseits wird trotzdem erwünscht!)

 

[AlArenal]

Vermutlich wurde in der Vorlesung erklärt, wie das Ganze grundsätzlich funktioniert. Weiterhin wurde vermutlich besprochen welche Variable genau für was steht. Ohne diese Infos ist es einigermaßen mühselig aus einem Stück ziemlich wirren und nichtssagenden Codes, erst wieder die Mathematik rauszuziehen und dann wieder zu überlegen, wie mans besser umsetzen kann, um es schlussendlich zu optimieren.

Als könnten wir mal eben auf nen Code schauen und *schwupps* haben wir die dahinterleigende Mathematik vor Augen. So ist es nicht. Irgendwo und irgendwann während der Vorlesung oder im Skript muss es mehr Infos geben als das oben von dir gezeigte. DIese Infos musst du aber schon liefern, die können wir uns ja nicht aus den Fingern saugen.

 

[KSG9|sebastian]

Ich hab nich gesagt dass ich den Thread sofort schließe. Ich hab nur das angesprochen was AlArenal auch gesagt hat: Ohne erklärung ist es mehr als mühselig den Code zu verstehen.

Ein paar Infos was welche Variable macht würde schon völlig reichen. Und diese Infos habt ihr in der Vorlesung doch sicher bekommen. Zu nem guten Umgang in nem Forum gehört auch, dass man bei Fragen sämtliche wesentlichen Infos gibt und nicht nur einen kleinen Teil (sofern Infos vorhanden sind).

 

[blubbiblubb]

gegeben:
• n Gegenstände mit Größen w_0, ...,w_(n−1) in IN und Gewinne P_0, ..., P_(n−1) in IN
• Rucksack der Kapazität B in IN

gesesucht:
- optimale Packung des Rucksacks, d. h. eine Teilmenge I  von { 0,...,n-1} mit sum_(i in I) w_i kleiner als B und maximalen Gewinn \sum_(i in I) P_i = max{ sum_(i in I') | I’ Teilmenge von { 0,...,n-1}, \sum_(i in I) w_i kleiner als B}


Beispiel:
Ein Dieb, der einen Safe ausräumt, findet in ihm N Gegenstände unterschiedlicher
Größe und unterschiedlichen Werts vor, hat aber nur einen kleinen
Rucksack mit Fassungsvermögen B um die Beute zu transportieren.
Das Rucksackproblem besteht darin eine Kombination der Gegenstände zu suchen,
die der Dieb für den Rucksack auswählen sollte, um den Gesamtwert der Beute zu
maximieren.


Gegenstände Größe w_i Gewinne P_i
0,...,5 3 4
6,...,9 4 5
10,11 7 10
12,13 8 11
14 9 13



verwende ein Feld A, wobei A[t] = normales Gewicht einer Packung von Gegenständen aus {0,...,i} mit Gewinn = t. Wir setzen A[t] = 1 (bzw. B+1), falls es keine Packung mit Gewinn = t und Gegenständen aus { 0,...,i} gibt.



So, mehr Infos habe ich leider nicht.

 

[A.T.]

Was hälst du davon wenn du uns erst mal eine Lauffähige Version des Codes gibtst und wir dann weiter gucken?

Weil das ding da oben ist ja der aller letzte Mist!

 

[blubbiblubb]

Sorry, das ist der Algorithmus aus der Vorlesung, aber ich mit dieser ganzen Sachen so überfordert, weil mir der Sinn überhaupt nicht klar ist.
Bitte helft mir!

 

[KSG9|sebastian]

Und schon gibts mehr Infos
Hab deinen Doppelpost gelöscht.
Habt ihr wirklich nur das Codestück bekommen ? Wenn ja, dann frag mal den Prof ob es ihm sonst noch gut geht.

 

[blubbiblubb]

So haben wir wirklich das Programm bekommen, ich werde ihm das morgen mal so sagen, dass das so nicht geht

 

[Beni]

Dein Prof hat hier dynamisches Programmieren angewandt. Das ist eine Methode um das Maximum einer rekursiven Formel zu berechnen, ohne alle Eingaben auszuprobieren.

Auf die Schnelle habe ich nicht viel brauchbares gefunden, vielleicht das hier.

Aber grundsätzlich geht es darum eine Tabelle aufzubauen: in den Spalten stehen IMHO die Preise, in den Zeilen die Objekte die mitgenommen werden, und in den Zellen das Gewicht. Es gibt eine Formel welche den Wert einer Zelle aus dem Wert einer anderen Zelle und dem Weg zwischen den beiden Zellen berechnet... ich kann nur empfehlen den Prof nochmal zu fragen, und das Problem dann selbst mal zu programmieren.

 

[blubbiblubb]

Das Problem ist nur, dass ich das ganze morgen vormittag schon benötige. Somit kann ic nicht den Prof. nochmal fragen.