Rucksackproblem mit Volumen, Wert & Gewicht

blume257

Guten Abend ihr Lieben,

ich schreibe bald eine Klausur und habe noch ein einziges Problem bei dem ich einfach nicht weiter weiß... Vielleicht kann mir einer von euch helfen?! Es geht um das Rucksackproblem, allerdings mit Wert, Volumen & Gewicht. Ich soll die Aufgabe im Pseudocode schreiben, habe es allerdings erst mal zu kompilieren versucht... folgender Code ist meiner:

Code

public static int[][] algo(int[] volumen, int[] gewicht, int [] wert,int volKapa, int gewKapa){


        int[][] c = new int[wert.length+1 ][gewKapa+1];
        for(int i=0;i<gewKapa;i++){
            c[i][0]=0;
        }


        for(int i=1;i<=wert.length;i++){
            for(int j=1;j<=gewKapa;j++){

                if(j<gewicht[i]    ||  j< volumen[i] {
                    c[i][j] =c[i-1][j];
                }
                else{

                    c[i][j] =Math.max(c[i-1][j], wert[i-1]+c[i-1][j-gewicht[i-1]]);
                }
            }
        }
        return c;
    }

Alles anzeigen

Allerdings funktioniert es einfach nicht für alle Eingaben und ich sitze schon einige Zeit daran, weiß nicht mehr weiter hab den Code schon gefühlte tausende Male geändert. Weiß jemand vielleicht meinen Fehler oder kennt einen guten Pseudocode? Ich wäre zu ewigem Dank verpflichtet!!

Liebe Grüße,
blume257

Ramses13

Zitat von blume257

Es geht um das Rucksackproblem, allerdings mit Wert, Volumen & Gewicht

Klingt mir etwas unvollständig.
Ich vermute mal, dass in den Rucksack Gegenstände reinkommen, wobei nach Wert maximiert werden soll und ein bestimmtes Volumen/Gewicht nicht überschritten werden soll? Wobei diese Gegenstände mit einer Flüssigkeit gefüllte Luftballons (o.ä) sind, damit die jede beliebige Form annehmen können und man beim Volumen die Abmessungen der Gegenstände nicht berücksichtigen muss?

Zitat

Allerdings funktioniert es einfach nicht für alle Eingaben und ich sitze schon einige Zeit daran, weiß nicht mehr weiter hab den Code schon gefühlte tausende Male geändert.

Zitat

Weiß jemand vielleicht meinen Fehler oder kennt einen guten Pseudocode? Ich wäre zu ewigem Dank verpflichtet!!

Den Code nach zu urteilen, wird versucht ein 2-dimensionales Array mit Werten zu füllen, d.h. das Problem wird versucht mittels dynamischer Programmierung zu lösen. Allerdings:
- Gewicht und Volumen sind zwei unterschiedliche Paar Schuhe, die 2. Dimension von c hat aber nur die Länge des Gewichts (ist also das Gewicht wertmäßig immer größer als das Volumen - bei nicht näher definierten Einheiten?)
- Ist dynamische Programmierung gefordert?
- Hast du schon mal versucht eine Lösung für Wert und Gewicht alleine (ohne Volumen) zu finden? Das könnte man dann ja versuchen auszubauen.

Hoffe es hilft.

Jetzt mitmachen!