Wie rekursiver Code ohne Memo, mit Memoization?

Ich weiß, was memoization ist aber diese rekursive Code mit:Wie rekursiver Code ohne Memo, mit Memoization?

int F(int n , int T){ 

    int ganancia ; 
    int maximum = INT_MIN; 



    if(T >= 0 && n == 0){ 

     maximum = 0; 

    }else if(T < 0){ 

     maximum = INT_MIN; 

    } else if(T >= 0 && n > 0){ 

     for(int i = 0 ; i <= m[n-1] ; i++){ 

      ganancia = i*v[n-1] + F(n- 1,T- i*t[n-1]); 

       if(ganancia > maximum){ 

        maximum = ganancia; 

       } 
     } 
    } 

    return maximum; 
}

Ich weiß nicht, wie in memoization zu verwandeln. Ich habe so etwas getan:

int F_alm(int n, int T){ 

    int ganancia ; 
    int maximum = INT_MIN; 

    //PETA POR ESTO 
    if(almacen_rec[n-1][T] != -1){ 

     return almacen_rec[n-1][T]; 

    }else if(T >= 0 && n == 0){ 

     maximum = 0; 

    }else if(T < 0){ 

     maximum = INT_MIN; 

    } else if(T >= 0 && n > 0){ 

     for(int i = 0 ; i <= m[n-1] ; i++){ 

      ganancia = i*v[n-1] + F(n- 1,T- i*t[n-1]); 

       if(ganancia > maximum){ 

        maximum = ganancia; 

       } 
     } 
    } 

    almacen_rec[n-1][T] = maximum; 
    return maximum; 

}

Das Ziel ist es, die Variable almacen_rec haben (es zuvor alle initialisiert wird als -1), wie dieses Bild:

lasse ich Ihnen die allgemeine Funktion der Übung :

Danke für Ihre Hilfe!

Quelle

2016-03-29 Quico Llinares Llorens

zurückgeben almacen_rec [n] [T]; sieht falsch aus: n-1? – willll

Oh ja! Gibt aber immer noch einen falschen Tisch zurück. Mein Programm gibt eine Memotabelle ohne Änderung zurück, alle Leerzeichen mit -1. Danke! –

Besser gesagt als vorher, mein Programm gibt alle Leerzeichen mit -1 außer dem Lösungsraum zurück, das ist richtig. Also mein Problem ist mit den Teilproblemen der Memoisierung, die nicht gelöst sind. –

Im Folgenden habe ich die Änderungen markiert, die zur Implementierung von Memoization in Ihrem Code mit // * erforderlich sind. Ich gehe davon aus, dass der Code in C++ ist, so dass ich std::pair und std::map aus der Standardbibliothek verwenden kann.

std::map<std::pair<int, int>, int> table; // * (A global variable) 

int F(int n , int T){ 

    // See if we've already computed this value 
    std::pair<int, int> pair(n, T); // * 
    if (table.find(pair) != table.end()) { // * 
     return table[pair]; // * 
    } // * 

    int ganancia ; 
    int maximum = INT_MIN; 



    if(T >= 0 && n == 0){ 

     maximum = 0; 

    }else if(T < 0){ 

     maximum = INT_MIN; 

    } else if(T >= 0 && n > 0){ 

     for(int i = 0 ; i <= m[n-1] ; i++){ 

      ganancia = i*v[n-1] + F(n- 1,T- i*t[n-1]); 

       if(ganancia > maximum){ 

        maximum = ganancia; 

       } 
     } 
    } 
    // Store the value so we won't have to compute it again later if needed 
    table[pair] = maximum; // * 
    return maximum; 
}

Quelle

2016-03-29 19:32:50 blazs

Wie rekursiver Code ohne Memo, mit Memoization?

Antwort

Verwandte Themen