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
und die Klasse: Packing
Vorgegeben habe ich folgende Methode, die implementiert werden soll:
Mein Code bis jetzt:
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
Java:
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
Java:
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:
Java:
*/
public static int pack(final Item[] items, final int capacity) {
// TODO Implement me!
return 0;
}
Mein Code bis jetzt:
Java:
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;
}}