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();
		}
	}
}