philippK

public class Rucksack implements RucksackProblemSolver {	      	private int[] elements;   	private int[][] matrix;   	private int rucksackSize;	public static void main (String[] args) {		Rucksack rucksack = new Rucksack();		if (args.length < 2) {			System.exit(0);		}		int[] eingabeElemente = new int[args.length - 1];		int[] partition;		for(int i = 0; i < eingabeElemente.length; i++) {			eingabeElemente[i] = Integer.parseInt(args[i]);		}		rucksack.setElements(eingabeElemente);		rucksack.setRucksackSize(Integer.parseInt(args[args.length-1]));		rucksack.buildMatrix();		rucksack.printMatrix();			partition = rucksack.getPartition(13);		System.out.println("Rucksacktest: " + rucksack.test(13));		for (int i = 0; i < partition.length; i++) {			System.out.println("Partitions-Element " + i + ":" + partition[i]);		}	}	public void setElements(int[] elements) {				if (elements == null) {			System.out.println("Nullpointer uebergeben\n Beende Programm!");			System.exit(0);		}					Arrays.sort(elements);				// Ausreichend das erste Element auf < 1 zu testen, da Array sortiert ist.		if (elements[0] < 1) {				System.out.println("Fehler, bitte Eingabeelemente ueberpruefen!");			System.exit(0);		}		this.elements = new int[elements.length];		for(int i = 0; i < elements.length; i++) {			this.elements[i] = elements[i];		}	}	public void setRucksackSize(int r) {		if (r >= 0)		   	rucksackSize = r;		else {		   	System.out.println("Sie haben eine negative Rucksackgroesse uebergeben!");			   	System.exit(0);		}	}		public void buildMatrix() {		matrix = new int[elements.length][rucksackSize + 1];				// Matrixelemente mit -1 initialisieren		for(int i = 0; i < elements.length; i++) {				// Zeilen			for (int j = 0; j < rucksackSize + 1; j++) {			// Spalten				matrix[i][j] = -1;			}		}		// Erste Zeile initialisieren:		matrix[0][0] = 0;	// Rucksack der Groeße 0 immer packbar		if (elements[0] <= rucksackSize)			matrix[0][elements[0]] = 1;	// Rucksack der Groesse erstes Element							// immer packbar inkl. erstem Element		// Restliche Zeilen initialisieren:		for(int i = 0; i < elements.length; i++) {				// Zeilen			for(int j = 0; j < rucksackSize + 1; j++) {			// Spalten				if(matrix[i][j] >= 0 && i < elements.length-1) {	// Wenn in einer Zeile ein Wert >-1 steht					matrix[i+1][j] = 0;				// so muss die Zelle daraunter den Wert 0 haben.					if(j + elements[i+1] <= rucksackSize)								matrix[i+1][j+elements[i+1]] = 1;					}			}		}		}	public boolean test(int rucksackSize) {				//Negative Rucksackgroesse -> Fehler				if (rucksackSize < 0) {			return false;		}		// Matrix noch nicht gebaut, oder 		// uebergebene Rucksackgroeße > momentane Rucksackgroesse		if (matrix[0][0] != 0 || rucksackSize > this.rucksackSize) {			setRucksackSize(rucksackSize);			buildMatrix();		}			return (matrix[elements.length-1][rucksackSize] > -1) ? true						                      : false;	}	public int[] getPartition(int rucksackSize) {				int[] temp_partition = new int[elements.length];		int i = 0;		// Falls sich der Rucksack ueberhaupt packen laesst:				if (test(rucksackSize) == true && rucksackSize > 0) {														// Ruecke bis zu der Zeile vor, in der sich das groesste in den			// Rucksack gehoerende Element befindet:						while (matrix[i][rucksackSize] != 1) {					i++;						}						int j = 0;			while(rucksackSize > 0) {				// Nachdem sich die Rucksackgroesse verkleinert hat ueberpruefe				// ruecke in die Ziele, die das naechste in den Rucksackg gehoerende				// Element enthaelt:								while(matrix[i][rucksackSize] != 1){							i--;								}				temp_partition[j] = elements[i];				rucksackSize -= elements[i];				j++;			}							int[] partition = new int[j];						for (int l = 0; l < j; l++) {				partition[l] = temp_partition[l];			}			Arrays.sort(partition);			return partition;		}		return new int[1];	}	   	public int[][] getMatrix(){		if (matrix[0][0] != 0)			buildMatrix();		   return matrix;	}		   	public void printMatrix() {		// Einfache Ausgabe:		/*		for(int i = 0; i < elements.length; i++) {			for(int j = 0; j < rucksackSize + 1; j++) {				System.out.print(matrix[i][j] + "\t");			}			System.out.println();		}		*/						// Rucksackgroessen printen		System.out.print("\nRucksackgroeße:\t\t");				for(int i = 0; i < rucksackSize + 1; i++) {			System.out.print("\t" + i);		}		// Matrix ausgeben		System.out.println("\n");		for(int i = 0; i < elements.length; i++) {			System.out.print("Elementgroeße: " + elements[i] + "\t");			for (int j = 0; j < rucksackSize + 1; j++) {				System.out.print("\t" + matrix[i][j]);			}			System.out.println();		}	}}