Not logged in. · Lost password · Register

Page:  1  2  next 
ri31hoky
Member since May 2011
452 posts
Subject: 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 vorinitialisiert

dynamisch (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
This post was edited 2 times, last on 2011-08-05, 11:43 by ri31hoky.
Maddoc
Avatar
Member since May 2011
526 posts
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...
ri31hoky
Member since May 2011
452 posts
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
This post was edited on 2011-08-05, 12:03 by ri31hoky.
ri31hoky
Member since May 2011
452 posts
    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
This post was edited on 2011-08-05, 12:13 by ri31hoky.
ri31hoky
Member since May 2011
452 posts
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));
        }
}




Diesmal stimmen nicht mal mehr die Werte überein o.O




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];
        }
}
This post was edited on 2011-08-05, 18:13 by ri31hoky.
Der Ich
93,333% Dipl.-Exzentriker
Avatar
Member since Oct 2006
3642 posts
n == k muss auch 1 ergeben,
eben so muss für jedes k == 0 1 rauskommen
* 01.10.2006, + 28.11.2011, † 31.01.2013
ri31hoky
Member since May 2011
452 posts
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
Maddoc
Avatar
Member since May 2011
526 posts
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 ...
Der Ich
93,333% Dipl.-Exzentriker
Avatar
Member since Oct 2006
3642 posts
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
* 01.10.2006, + 28.11.2011, † 31.01.2013
ri31hoky
Member since May 2011
452 posts
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 :D
This post was edited on 2011-08-06, 11:41 by ri31hoky.
ri31hoky
Member since May 2011
452 posts
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
return lin(1+(((a-b)*c)%100), a, b, steps-1);
zumindest richtig sein



Edit: die Überlegung war


                                    f(5)

                      /               |                \

                  f(4)            f(3)            f(2)

          /         |         \

       f(3)     f(2)      f(1)

   /    |    \

f(2) f(1) f(0)
This post was edited on 2011-08-07, 21:34 by ri31hoky.
Der Ich
93,333% Dipl.-Exzentriker
Avatar
Member since Oct 2006
3642 posts
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);
}
* 01.10.2006, + 28.11.2011, † 31.01.2013
This post was edited on 2011-08-07, 22:05 by Der Ich.
ri31hoky
Member since May 2011
452 posts
Ah ok dann doch von oben nach unten danke
Der Ich
93,333% Dipl.-Exzentriker
Avatar
Member since Oct 2006
3642 posts
Quote by ri31hoky:
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
* 01.10.2006, + 28.11.2011, † 31.01.2013
ri31hoky
Member since May 2011
452 posts
Danke hab ich und wusst ich  ;-)
Close Smaller – Larger + Reply to this post:
Verification code: VeriCode Please enter the word from the image into the text field below. (Type the letters only, lower case is okay.)
Smileys: :-) ;-) :-D :-p :blush: :cool: :rolleyes: :huh: :-/ <_< :-( :'( :#: :scared: 8-( :nuts: :-O
Special characters:
Page:  1  2  next 
Go to forum
Datenschutz | Kontakt
Powered by the Unclassified NewsBoard software, 20150713-dev, © 2003-2011 by Yves Goergen