Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Dynamische Programmierung
Wo ist der Fehler, es kommen die gleichen Ergebnisse raus, aber viel Dynamik ist da nicht drinnen…
Im Prinzip muss man doch bei dynamischer Programmierung nur schauen:
- habe ich den Wert schon berechnet? (im Array)
ja → returne Wert
nein → mache das gleiche wie beim naiven, nur dass das Ergebnis im Array gespeichert wird
Aber irgendwas scheine ich noch zu vergessen, da ich nie auf Anhieb den korrekten Code habe o.O
naiv
private static int knapsack(int[] items, int capacity){
int maxValue = 0;
for (int i = 0; i< items.length; i++) {
int spaceLeft = capacity - items[i];
if (spaceLeft >= 0) {
int value = knapsack(items, spaceLeft) + items[i];
if (value > maxValue) {
maxValue = value;
}
}
}
return maxValue;
}
private static int[] maxKnown = new int [MAX]
// mit -1 vorinitialisiertdynamisch (oder auch nicht)
private static int knapsack2 (int[] items, int capacity) {
if (maxKnown[capacity] != -1) {
return maxKnown[capacity];
}
int maxValue = 0;
for (int i = 0; i<items.length; ++i) {
int spaceLeft = capacity - items[i];
if(spaceLeft >= 0) {
int value = knapsack2(items, spaceLeft) + items[i];
if (value > maxValue) {
maxValue = value;
if(maxValue <= capacity){
maxKnown[maxValue] = maxValue;
}
}
}
}
return maxValue;
}Edit: Die Aufgabe ist von der Klausuraufgabe leicht abgewandelt, statt Item[] hab ich einen int[] Array genommen
Was du noch machen könntest, wäre eine Abfrage vor dem rekursiven Aufruf reinzubasteln, der prüft ob es den Wert schon gibt. Damit wären es ein paar Aufrufe weniger, aber sonst…
Die Frage bei der b) ist, warum wäre selbst eine iterative Version inzeffizient und ich nehme an, da trotzdem alle Variationen durchprobiert werden, auch wenn maxValue == capacity ist. Vielleicht da noch irgendwie nen Abbruch einbauen? Ich probier mal ein bisschen rum.
Edit: wobei das eigentlich nicht die Lösung sein kann, da die dynamische Programmierung ja auch schneller sein muss, wenn das Maximum zb capacity - 1 ist
private static int knapsack2(int[] items, int capacity) {
if (maxKnown[capacity] != -1) {
return maxKnown[capacity];
}
int maxValue = 0;
for (int i = 0; i<items.length; ++i) {
int spaceLeft = capacity - items[i];
if(spaceLeft >= 0) {
int value;
if(maxKnown[spaceLeft] == -1){
value = knapsack2(items, spaceLeft) + items[i];
} else { value = maxKnown[spaceLeft]; }
if (value > maxValue) {
maxValue = value;
if(maxValue <= capacity){
maxKnown[maxValue] = maxValue;
}
}
}
}
return maxValue;
}Du hattest recht so funktioniert es. Macht auch sinn die Abfrage vor dem rekursiven Aufruf zu machen 
Danke
Edit:
auch wenn es in der Klausur wohl irgendwie anders gedacht war, weil da ziemlich viel Platz vor dem return ist, dafür nur ziemlich wenig in der for-Schleife
Jemand ne Idee wo der Fehler in pascalNiceRek(H) liegt.
Laut Angabe soll in pascalNiceRek vor die for-Schleife auch etwas, ich wüsste allerding nicht was
static long[] pascalBadRek(int n){
long[] result1 = new long [n+1];
for (int k=0; k<=n; k++){
result1[k]= pascalBadRekH(n,k);
}
return result1;
}
static long pascalBadRekH (int n, int k) {
if (n<0||k<0||k>n){
return 0;
} else if (n == 0 && k == 0){
return 1;
} else {
return (pascalBadRekH(n-1, k-1) + pascalBadRekH (n-1,k));
}
}
static long[] pascalNiceRek(int n){
long[] result = new long[n+1];
for (int k = 0; k<=n; k++){
result[k] = pascalNiceRekH(n, k, result);
}
return result;
}
static long pascalNiceRekH(int n, int k, long[] result){
if (n<0 || k<0 || k>n){
return 0;
}
if (n == 0 && k == 0){
return 1;
}
if (result[k] != 0) {
return result[k];
}
else {
result[k] = pascalNiceRekH(n-1, k-1, result) + pascalNiceRekH (n-1, k, result);
return result[k];
}
}n == k muss auch 1 ergeben,
eben so muss für jedes k == 0 1 rauskommen
Das funktioniert auch nicht.
Das Problem ist wohl, dass die Referenz immer auf das selbe Array zeigt und ich somit in der Rekursion, auf die gerade berechneten Werte zugreife
So kommt für n=3 z.B.
1 3 4 1
statt
1 3 3 1
raus, weil statt auf
1 2 1 von der Vorzeile, auf die überschriebene erste Stelle 1 3 1 zugegriffen wird.
Oder lieg ich hier falsch
Irgendwas stimmt mit deiner dynamisches Programmierung nicht. Es werden zwar irgendwie Werte berechnet und gespeichert, allerdings in einem eindimensionalem Array auf dem dauernd zugegriffen wird, auch für Werte von n die nicht mehr dem original entsprechen.
Probiers doch mal mit einem zwei dimensionalem Array, eine Zeile pro möglichen n Wert. Irgendwo auf eine Klausur gabs da auch ein schönes Bidchen von den Pascal Zahlen, dass du dir genau die Zahlen speicherst. Vielleicht klappts dann …
Ja das habe ich aus offensichtlichkeit komplett übersehen, das muss natürlich ein 2D-Array sein, da Binomialkoeffizienten von 2 Parametern abhängen, omg failaments
Ok so ists easy, macht auch irgendwo Sinn
Edit: Was mir durch die Aufgabe klar geworden ist, wenn da ein Kasten auf dem Blatt ist, dann sollte man da auch was reinschreiben 
Zwar nicht wirklich dynamische Programmierung aber immerhin Durchreichen von Zwischenergebnissen.
Klausur 19.02.2009
public static int f2(int n){
return lin(1,2,3,n);
}
public static int lin(int a, int b, int c, int steps){
if (steps<3){
return a;
}
else {
return lin(1+(((a-b)*c)%100), a, b, steps-1);
}
}Die Abbruchbedingung ist wohl falsch, aber keine Ahnung wie sie sonst soll
Laut meiner Überlegung müsste [quote]
return lin(1+(((a-b)*c)%100), a, b, steps-1);
[/quote] zumindest richtig sein
Edit: die Überlegung war
f(5)
/ | \
f(4) [b] [u] f(3)[/u] [u]f(2)[/u][/b]
/ | \
[b]f(3) [/b] [b]f(2)[/b] f(1)
/ | \
f(2) f(1) f(0)
Das ist verkehrt:
Richtig ist:
lin(int a, int b, int c, int steps) {
return steps == 0 ? a : lin(b,c,1+(((c-b)*a)%100),steps-1);
}Ah ok dann doch von oben nach unten danke
hättest du übrigens testen können indem dus mal abgetippt hättest 
dann hättest du gesehen dass deins grütze ist
Danke hab ich und wusst ich 
Doch nicht so klar wie ich dachte. Also das b,c ist mir klar, da man ja erst rekursiv absteigt bis zum Basisfall.
Aber wie man jetzt das Ergebnis zusammenbaut, versteh ich nicht so ganz
Warum
1+(((c-b)*a)%100Man ist doch jetzt nach ganz unten abgestiegen
sagen wir:
f(2) f(1) f(0)
wobei f(2) das „alte“ b ist und f(1) das „alte“ c
Was man jetzt daraus berechnen will ist ja f(3), um wieder rekursiv aufzusteigen
Also eigentlich ganz normal f(3) = (((f(2) - f(1)) * f(0)) % 100) (Jetzt mal davon abgesehen, dass n>2 sein sollte)
Wieso jetzt c - b
Das wäre ja f(1) - f(2) …
Bevor wieder Kritik kommt Ich hab die Aufgabe in Eclipse und weiß, dass deine Lösung richtig ist, nur würde ich das auch gerne verstehen
c ist der Wert vor einem Zeitschritt f(n-1)
b ist der Wert vor 2 Zeitschritten f(n-2)
a ist der Wert vor 3 Zeitschritten f(n-3)
a = f(0) = 1
b = f(1) = 2
c = f(2) = 3
wenn ich nun f(3) haben will, brauche ich f(3) = 1+(((f(2) - f(1)) * f(0)) % 100)
c ist der Wert vor einem Zeitschritt f(n-1)
b ist der Wert vor 2 Zeitschritten f(n-2)
a ist der Wert vor 3 Zeitschritten f(n-3)Genau hier liegt das Problem
Wo seh ich das?
wegen dem
return lin (1,2,3,n) ?
Meinem schönen Baum zufolge ist es nämlich genau andersrum
ja