Java Rucksackproblem mit Wert, Volumen & Gewicht

[kartoffelchip]

Guten Morgen, ich habe ein Problem mit einem Programm. Bei dem Programm geht es um dynamische Programmierung. Genauer gesagt das Rucksack-Problem, allerdings mit Volumen, Gewicht und Wert. Nun habe ich diesen Code entwickelt, allerdings spuckt er nicht für alle Zahlen das richtige Ergebnis aus. Kann mir da jemand helfen?

public class volGewDyn
{
public static void main(String[] args){
  int[][] erg;
  int [] volumen = {1,3,1,1};
  int[] gewicht={1,2,1,1};
  int[] wert={5,3,6,5};
 int volkapa=2;
 int gewKapa=2;
  erg=Algo(volumen,gewicht,wert,volkapa,gewKapa);

          
             for(int i=0;i<gewicht.length;i++){
                 for(int j=0;j<Math.max(gewKapa,volkapa);j++){
                     System.out.print(erg[i][j]+("  " ));
                    }
                    System.out.println();
}
        
    }



public static int[][] Algo(int [] volumen, int [] gewicht, int[] wert , int volkapa,int gewKapa){

    int[][] c= new int[gewicht.length+1][Math.max(gewKapa,volkapa)+1];


    for(int j=0;j<Math.max(gewKapa,volkapa)+1;j++){
        c[0][j]=0;
    }
    
    for(int i=1;i<gewicht.length;i++){
        for(int j=0;j<Math.max(gewKapa,volkapa)+1;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]]) );
            
        }
        }
    }
    return c;
}
}

 

[#basTi]

1. Was ist das Rucksackproblem?
2. Was ist die Aufgabe?
3. Code in den entsprechenden BB Code markieren.
4. Klingt nach Hausaufgabe: Wird nicht beantwortet.

-> Alles falsch gemacht

 

[kartoffelchip]

Das Rucksackproblem dürfte eigentlich jedem bekannt sein da es ein Klassiker für den einstieg in die dynamische programmierung ist .Die aufgabe ist also den möglichst besten wert zu erzielen .Und nein es sind keine hausaufgaben ich bin Student und bereite mich auf die klausur vor

 

[firexs]

Ich hab zwar lange nicht mehr damit zu tun gehabt, vermute aber mal mit zugekniffenen Augen, das die Variablen nicht Global sind. Dh. in jedem Abschnitt sind es neue Variablen.

lg
fire

 

[baizon]

Ohne BB Code gebe ich keine Hilfestellung

 

[kartoffelchip]

bb code ?

 

[baizon]

Das wäre ein Beispiel...

public class Beispiel {
 public static void main(String[] args) {
  System.out.println("Beispiel");
}

 

[Eisbrecher99]

erledigt

 

[AppLeYArD]

Sonst auch hier nachzulesen. Unabhängig von deinem Code, das Rucksack-Problem ist mir auch unbekannt ^^

 

[kartoffelchip]

Vielen Dank für die Erklärung
Habe ich gemacht, hoffe ist so jetzt richtig '
Um nochmal aufs Rucksackproblem zu sprechen zu kommen, erkläre ich es schnell noch mal:
Man hat n verschiedene objekte mit einem gewicht und einem wert. Außerdem hat meine einen Rucksack mit einer Kapazität .
Nun will man den möglichst größten wert erreichen der in den rucksack passt

 

[-Razzer-]

Bei dir hat ein Gegenstand aber einen Wert + Volumen + Gewicht
Du könntest auch einfach nach Wert/Volumen oder Wert/Gewicht sortieren und dann solange füllen, bis die Grenze erreicht ist unter der Berücksichtigung der anderen Grenze, da du ja 2 Nebenbedingungen hast Gewicht und Volumen.

Ich weis nicht warum du ein Matrix hierfür verwendest.

 

[kartoffelchip]

Da dies nicht immer zur richtigen lösung führt sondern nur greedy ist . Die matrix verwnde ich um es dynamisch zu machen

 

[maxwell-cs]

bin ehrlich gesagt jetzt nicht motiviert den code durchzugehen, aber:

gerade dynamic-programming-algorithmen lassen sich doch hervorragend debuggen.
minimalbeispiel konstruieren, bei dem was schief läuft, und dann nachvollziehen, wo teillösungen nicht mehr optimal sind.

 

[rob-]

Rucksackproblem kenne ich. Ist praktisch eine Übung zu Bäumen. Bei uns kam das vor dem Suchbaum, B-Baum etc., was sinnlos war, da der Rucksack am härtesten zu programmieren ist wegen "doppelter" Rekursion, also 2 Aufrufe in Folge. Aber Code dieses Kalibers wird NIEMALS in der Klausur kommen. Lerne lieber was das passiert und warum.

Da geht es um die Arten der Befüllung, also immer nur die wertvollsten Sachen einzupacken, oder die Leichtesten. Lokal optimal da für jeden Schritt immer geschaut wird was das nächst beste ist, heißt aber nicht dass es insgesamt optimal ist. Nur durch Rekursion, also die Kombination ALLER möglichen Werte wirst du das globale Optimum bekommen, also der finale Rucksackwert unter Beachtung der Kapazitäten (Gewicht). Wenn du es zeichnest, hast du immer die Frage "nächstes item einpacken, ja / nein"? Dadurch ensteht ein Baum mit Pfaden.

Wenn man das 1 Mio mal machen lässt, mit random erzeugten Arrays, ist das rekursive 100% optimal.
Vergleicht man das packen nach Wert und Gewicht, so ist das Packen nach Wert zu ~70% besser als nach Gewicht.
Wenn ihr Koffer packt, immer das wertvollste rein :>

Wenn du nicht weiter kommst, frag Google nach Rucksack.java
Die Profs schreiben alle voneinander ab...

---

Für den Rest: Ihr wollt einen Geldautomaten programmieren der überschüssiges Geld zurück zahlt, mit so wenigen Münzen wie möglich (soll optimal ausgelastet werden). Sagen wir man hat 16 Cent Rückgeld. Es gibt die Münzen: 12, 5, 1, die Wertvollste ist auch die Schwerste vom Material her.

Greedy nach Wert gibt also zurück: 12, 1, 1, 1, 1
Greedy nach Gewicht: 1, 1, 1, 1, 1, 1.........
Optimal ist aber: 5, 5, 5, 1

Anders gesagt, die Betrachung von A->B ist hier nicht ausreichend. Mit einer for Schleife wird es daher sehr hart das Optimum zu ermitteln, bzw. es ist aufwändig und danach nur auf einen Münzsatz beschränkt. Per Rekursion lässt sich allerdings jede mögliche Kombination probieren, die mit den wenigsten Münzen gewinnt.