Rucksackproblem lösen

[Fabian94]

Ich habe nur Zeile 1 bis 144.

 

[vfl_freak]

Ich habe nur Zeile 1 bis 144.

Dann liegt Dein Fehler genau 13 Zeilen HINTER Deinem Code

VG Klaus

 

[Fabian94]

So, ich habe jetzt ein wenig rumprobiert und es wird in den Tests kompiliert und ich bekomme "nur" noch OutOfBoundsExceptions. Bei 13 Testläufen bekomme ich 6 Fehler angezeigt. Vielleicht sehr ihr auf den ersten Blick einen Fehler.

Mein Code:

package ads.set2.knapsack;


public class KnapsackSolver {

    static int capacity;
    static int Laenge; 
    static int [] gProfit;
    static int [] gGewicht;
    static int[] [] matrix;
   

    public static Packing pack(final Item[] items,final int capacity){
       
        KnapsackSolver.Laenge= items.length;
        Packing Ergebnis = new Packing(); 

       
        int[] ArrayX = new int [Laenge];
        int[] ArrayY = new int [Laenge];
   
        for(int i=0; i<items.length; i++){
           
            ArrayX[i]= items[i].getProfit();
            ArrayY[i]= items[i].getWeight();

        }
       
        KnapsackSolver.gProfit = ArrayX.clone(); 
        KnapsackSolver.gGewicht = ArrayY.clone();
        KnapsackSolver.capacity= capacity;
       
   
       
        matrix = initMatrix();

        int erg = packen(capacity,0);

       
        int aktVol = 0;
       

           
        for(int i = 0; i<matrix.length; i++){
            if(matrix[i][0]==erg){
                aktVol = i;               
                }
            }
           
       
            for(int i = 0; i<gGewicht.length; i++){
                if(aktVol-gGewicht[i]>= 0 && matrix[aktVol-gGewicht[i]][i+1]==matrix[aktVol][i]-gProfit[i]){


                   
                    Ergebnis.getItems().add(items[i]);
                      Ergebnis.setProfit(Ergebnis.getProfit()+items[i].getProfit());
   
                    aktVol = aktVol-gGewicht[i];
               
                }
            }
        return Ergebnis;      
  }

   
    static int[][] initMatrix() {
       
        int[][] m = new int[capacity+1][gGewicht.length];
       
        for(int i = 0; i<m.length; i++){
           
            for (int j = 0; j<m[0].length; j++){
                m[i] [j] = -1;
            }   
            }
        return m;
        }
       
   
   
    // Restvolumen: das was über bleibt, wenn wir uns für einen Gegenstand entschieden haben
       
   
    static int packen(int restVol, int i){
       
       
        if(i<gGewicht.length){
           
            if(matrix[restVol][i]!=-1) {
                return matrix[restVol][i];
               
            }
            //nicht einpacken
            int nicht = packen(restVol, i + 1);
           
            //einpacken
            int drin = 0;
           
           
            if(restVol - gGewicht[i] >= 0){
                drin = gProfit[i] + packen(restVol-gGewicht[i], i+1);
            }
            if(nicht>drin) {
        //        return nicht;
                matrix[restVol][i] = nicht;
            }else{
        //        return drin; 
                matrix[restVol][i] = drin;
           
            }
           
        return matrix[restVol][i];}
        return 0;
               
            }       
    }

Die Fehler die er zeigt,

  There were 6 failures:
  1) test0(ads.set2.knapsack.test.KnapsackTest)
  java.lang.ArrayIndexOutOfBoundsException: 5
  ?at ads.set2.knapsack.KnapsackSolver.pack(KnapsackSolver.java:52)
  ?at ads.set2.knapsack.test.KnapsackTest.performTests(KnapsackTest.java:157)
  ?at ads.set2.knapsack.test.KnapsackTest.test0(KnapsackTest.java:57)
  2) test1(ads.set2.knapsack.test.KnapsackTest)
  java.lang.ArrayIndexOutOfBoundsException: 10
  ?at ads.set2.knapsack.KnapsackSolver.pack(KnapsackSolver.java:52)
  ?at ads.set2.knapsack.test.KnapsackTest.performTests(KnapsackTest.java:157)
  ?at ads.set2.knapsack.test.KnapsackTest.test1(KnapsackTest.java:62)
  3) test2(ads.set2.knapsack.test.KnapsackTest)
  java.lang.ArrayIndexOutOfBoundsException: 10
  ?at ads.set2.knapsack.KnapsackSolver.pack(KnapsackSolver.java:52)
  ?at ads.set2.knapsack.test.KnapsackTest.performTests(KnapsackTest.java:157)
  ?at ads.set2.knapsack.test.KnapsackTest.test2(KnapsackTest.java:67)
  4) test3(ads.set2.knapsack.test.KnapsackTest)
  java.lang.ArrayIndexOutOfBoundsException: 10
  ?at ads.set2.knapsack.KnapsackSolver.pack(KnapsackSolver.java:52)
  ?at ads.set2.knapsack.test.KnapsackTest.performTests(KnapsackTest.java:157)
  ?at ads.set2.knapsack.test.KnapsackTest.test3(KnapsackTest.java:72)
  5) test4(ads.set2.knapsack.test.KnapsackTest)
  java.lang.ArrayIndexOutOfBoundsException: 10
  ?at ads.set2.knapsack.KnapsackSolver.pack(KnapsackSolver.java:52)
  ?at ads.set2.knapsack.test.KnapsackTest.performTests(KnapsackTest.java:157)
  ?at ads.set2.knapsack.test.KnapsackTest.test4(KnapsackTest.java:77)
  6) test8(ads.set2.knapsack.test.KnapsackTest)
  org.junit.runners.model.TestTimedOutException: test timed out after 500 milliseconds

  FAILURES!!!
  Tests run: 13,  Failures: 6

Die Zeile: 51-52

            for(int i = 0; i<gGewicht.length; i++){
                if(aktVol-gGewicht[i]>= 0 && matrix[aktVol-gGewicht[i]][i+1]==matrix[aktVol][i]-gProfit[i]){

Die Zeile: 57

Ergebnis.setProfit(Ergebnis.getProfit()+KnapsackSolver.gProfit[i]);