# Rucksackproblem lösen



## Fabian94 (17. Mai 2017)

Hallo,

ich habe eine lange Hausaufgabe auf und komme nicht so recht weiter. 
Ich habe 2 Klassen gegeben und soll eine dritte Klasse zum lösen des Rucksackproblems schreiben. 
Mein Problem liegt vor allem in der geforderten Rückgabe, in der Form einer Instanz von Packing.
Weiß gar nicht wie ich es so ausgeben kann.  
Bzw. sagen, wir es mal so, das Programm klappt mit eigenen Testfällen, wird aber bei den automatischen noch nicht mal kompiliert. :/ Vielleicht könnt ihr mir ein paar Tipps geben. Ich will keine Musterlösung oder so, aber komme halt nicht weiter.  

Klasse: Item


```
public class Item {

/** Profit gained by packing this item into the knapsack. */

private final int profit;

/** Weight of this item. */

private final int weight;


public Item(final int profit, final int weight) {

if (profit < 0) {

throw new IllegalArgumentException("profit cannot be negative.");

}


if (weight < 0) {

throw new IllegalArgumentException("weight cannot be negative.");

}


this.profit = profit;

this.weight = weight;

}


public int getProfit() {

return profit;

}

public int getWeight() {

return weight;

}}
```

und die Klasse: Packing 
	
	
	



```
import java.util.ArrayList;
import java.util.Collection;

/**

 * A packing of a knapsack. A packing is specified by a list of items to be

 * packed and the profit generated by packing them. To use this class, create a

 * new instance, call {@link #setProfit(int)} to set the profit, and call

 * {@link #getItems()} to obtain the list of items in this packing and add items

 * to it.

 */

public class Packing {

private Collection<Item> items = new ArrayList<>();

private int profit = 0;


public int getProfit() {

return profit;

}


public void setProfit(final int profit) {

if (profit < 0) {

throw new IllegalArgumentException("profit cannot be negative.");

}

this.profit = profit;

}


/**

* Returns the list of items in this packing. The returned list can be

* modified to add more items.

*/

public Collection<Item> getItems() {

return items;
}
}
```


Vorgegeben habe ich folgende Methode, die implementiert werden soll: 
	
	
	



```
*/
public static int pack(final Item[] items, final int capacity) {
   // TODO Implement me!
   return 0;
}
```


Mein Code bis jetzt: 

```
public class KnapsackSolver  {
     static int capacity;
    static int Länge; 
    static int [] gVol;
    static int [] gWert;
    static int[][] matrix;
   
    public static int pack(final Item[] items, int capacity){     
        KnapsackSolver.Länge= items.length;
       
        int[] ArrayX = new int [Länge];
        int[] ArrayY = new int [Länge];
   
        for(int i=0; i<items.length; i++){
       
            ArrayX[i]= items[i].getWeight();
            ArrayY[i]= items[i].getProfit();
        }
        KnapsackSolver.gWert = ArrayX.clone(); 
        KnapsackSolver.gVol = ArrayY.clone();
        KnapsackSolver.capacity= capacity;
       
        matrix = initMatrix();
        int erg = packen(capacity,0);
        findG(erg);
       
        Packing Ergebnis = new Packing(); 
        Ergebnis.getItems();
       
        return 0;      
  }

    static int[][] initMatrix() {
       
        int[][] m = new int[capacity+1][gVol.length];
       
        for(int i = 0; i<m.length; i++){
           
            for (int j = 0; j<m[0].length; j++){
                m[i] [j] = -1;
            }         
            }
        return m;
        }
       
        static void findG(int maxWert){
            int aktVol = 0;
            int aktVol2=0;
           
            for(int i = 0; i<matrix.length; i++){
                if(matrix[i][0]==maxWert){
                    aktVol = i;
                 
               
                }
            }
            for(int i = 0; i<matrix.length; i++){
                if(matrix[i][0]==maxWert){
                    aktVol2 = i;
                   
                }}
           
            System.out.println("Gegenstände:");
            for(int i = 0; i<gVol.length; i++){
                if(aktVol-gVol[i]>= 0 && matrix[aktVol-gVol[i]][i+1]==matrix[aktVol][i]-gWert[i]){
               
                    System.out.print(i+" ");
                    aktVol = aktVol-gVol[i];        
                }
            }

           
            System.out.println("\nMaximal erreichter Profit:");
           
            for(int j = 0; j<gVol.length; j++){
                if(aktVol2-gVol[j]>= 0 && matrix[aktVol2-gVol[j]][j+1]==matrix[aktVol2][j]-gWert[j]){
               
                  //  int Wert = gWert[j];
                  //if(j==0){Wert=gWert[j];
                  // }else{
                 //   Wert += gWert[j-1];
                  //}        
                    //        int Wert = 0;
                    //Wert =  Wert + gWert[j];
                   
                    System.out.print(gWert[j] + " ");

                    aktVol2 = aktVol2-gVol[j];
                }} }
       
  static int packen(int restVol, int i){
        if(i<gVol.length){
           
            if(matrix[restVol][i]!=-1) {
                return matrix[restVol][i];
               
            }
            //nicht einpacken
            int nicht = packen(restVol, i + 1);
           
            //einpacken
            int drin = 0;
            if(restVol - gVol[i] >= 0){
                drin = gWert[i] + packen(restVol-gVol[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;   
            }}
```


----------



## abdellaui (17. Mai 2017)

So am Rande: Umlaute in einem Variabel sind ungültig.
PS: Länge


----------



## sheel (17. Mai 2017)

Hi

Kannst du den Kommentar zu pack auch noch herzeigen?
Speziell, was soll da zurückgegeben werden? 0 wohl eher nicht...

Und was soll dein Algo eigentlich machen, wenn er richtig ist?



> Bzw. sagen, wir es mal so, das Programm klappt mit eigenen Testfällen, wird aber bei den automatischen noch nicht mal kompiliert. :/


Fehlermeldungen und -stelle?


----------



## vfl_freak (17. Mai 2017)

Moin,



abdellaui hat gesagt.:


> Umlaute in einem Variabel sind ungültig


Deklarieren darfst Du sie schon ... schön ist es allerdings nicht!
Aber es ist oben eh' nicht sehr kosenquent Englisch oder Deutsch .... 

VG Klaus


----------



## Fabian94 (17. Mai 2017)

Schön ist bei dem Code noch gar nichts   Aber ich probiere auch nur rum. 
Null soll zurückgeben werden. 

Das hier ist die gesamte Aufgabenstellung: 

"Die zur Verfügung stehenden Einträge werden durch Instanzen der Klasse Item beschrieben, die Sie hier herunterladen können. Das Ergebnis soll als Instanz der Klasse Packing zurückgeliefert werden, die Sie hier herunterladen können. Sie besteht aus dem maximal erreichbaren Profit sowie einer Auflistung von Gegenständen, welche zu diesem Profit führen ohne die Maximalkapazität des Rucksacks zu überschreiten. Ihre Abgabe sollte lediglich aus der Klasse KnapsackSolver bestehen."


```
*/
public static int pack(final Item[] items, final int capacity) {
   // TODO Implement me!
   return null;
}
```



Fehler der mir angezeigt wird : 
*Ausgabe des Compilers*
*There was an error during compilation of the program.* This usually indicates some problem with the class names. Please ensure that you use *exactly the same name* as required in the assignment. Additionally you should ensure that you *only use a package when you are asked to do so*.

The following error log was generated during compilation:

  /tmp/SPdGYJ7TMQ/ads/set2/knapsack/test/KnapsackTest.java:157: error: incompatible types: int cannot be converted to Packing
  ??Packing solution = KnapsackSolver.pack(items, instance.maxWeight);
  ??                                      ^
  1 error


----------



## vfl_freak (17. Mai 2017)

Moin,
steht doch da:


Fabian94 hat gesagt.:


> /tmp/SPdGYJ7TMQ/ads/set2/knapsack/test/KnapsackTest.java:157: error: incompatible types: int cannot be converted to Packing
> ??Packing solution = KnapsackSolver.pack(items, instance.maxWeight);


Deine Rückgabe 'int' kann (logischerweise) nicht in ein Object 'Packing' konvertiert werden!
Wo ist denn Zeile 153 ???

VG Klaus


----------



## Fabian94 (17. Mai 2017)

Zeile 153 hab ich nicht.


----------



## sheel (17. Mai 2017)

Mit dem Fehler wäre mal ziemlich deutlich, dass pack() "kein" int zurückgeben soll... den Kommentar dazu seh ich leider noch immer nicht (der Kommentar, von dem man das schließende */ erkennen kann).

Und eine deutsche Beschreibung, was dein Algorithmus eigentlich machen "soll", statt dass wir uns das am nicht funktionierenden Code zusammenraten müssen...


----------



## Fabian94 (17. Mai 2017)

Tschuldige, ich bastel noch ein bisschen rum und melde mich sonst nochmal.


----------



## vfl_freak (17. Mai 2017)

Fabian94 hat gesagt.:


> Zeile 153 hab ich nicht.


sorry, meinte _*157*_ !!

VG Klaus


----------



## Fabian94 (17. Mai 2017)

Ich habe nur Zeile 1 bis 144.


----------



## vfl_freak (17. Mai 2017)

Fabian94 hat gesagt.:


> Ich habe nur Zeile 1 bis 144.


 

Dann liegt Dein Fehler genau 13 Zeilen HINTER Deinem Code 

VG Klaus


----------



## Fabian94 (17. Mai 2017)

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]);
```


----------

