Rucksack Problem Algorithmus

This site uses cookies. By continuing to browse this site, you are agreeing to our Cookie Policy.

  • Aus einer Menge von Objekten, die jeweils ein Gewicht und einen Nutzenwert haben, soll eine Teilmenge ausgewählt werden, deren Gesamtgewicht eine vorgegebene Gewichtsschranke nicht überschreitet. Unter dieser Bedingung soll der Nutzenwert der ausgewählten Objekte maximiert werden.

    Table Of Contents

    Rucksack Problem oder auch "Knapsack Problem".
    Am Rucksack Problem kann man die Vorteile des Backtrackings aufzeigen, da hier das globale Optimum gesucht wird.

    Beispiel Backtracking

    Source Code

    1. public static void main(String[] args) {
    2. int[] werte = new int{5,4,3,2,1};
    3. int[] gewichte = new int{10,5,20,30,15};
    4. }
    6. public static int rucksack(int i, int kap, int wert) {
    7. if ((i >= n) || (kap <= 0))
    8. return wert;
    9. if (gewichte[i] > kap)
    10. return rucksack(i+1,kap,wert);
    11. int mit=rucksack(i+1, kap-gewichte[i], wert+werte[i]);
    12. int ohne=rucksack(i+1, kap, wert);
    13. return max(mit, ohne);
    14. }
    Display All



    Weblinks

    16,945 times viewed