/*Toronyépítés: a legmagasabb torony
Bemenet:
?n kocka, Mi méretű, Si súlyú
Feltétel:
nagyobb kocka kisebbre nem tehető
nehezebb kocka könnyebbre nem tehető
Kimenet:
a torony magassága
*/
public class toronyrek{
	static int      suly[] ={5,8,9,11,7,3,2}; 
	static int 		meret[]={1,7,8, 6,3,9,5,}; 
	static class torony{
			int magassag;
			int utolso_merete;
		torony(){magassag=0;utolso_merete=0;}
	}
///////////////////////////////////////////////////////////////////////////
//Ötlet:rendezzük a kockákat súly szerint csökkenő sorrendbe
	public static void rendez(int k){
		int i,j,ss,sm;
		for (i=0;i<=k;i++)	for (j=i+1;j<=k;j++){
			if (suly[i]<suly[j]) {//csere
				ss=suly[i];sm=meret[i];
				suly[i]=suly[j];meret[i]=meret[j];
				suly[j]=ss;	meret[j]=sm;
			}
		}
	}	
//ekkor a kockasorozat egy részsorozata a megoldás

	public static torony epit(int k){
		torony max= new torony();
		int i;
		int magassag,utolso_merete;
		max.magassag=meret[k];
		max.utolso_merete=meret[k];
		if (k==0) return max;  //bázis eset
		for (i=0; i<k;i++){
			magassag=epit(i).magassag;
			utolso_merete=epit(i).utolso_merete;
			if (magassag>max.magassag){ //a k-adik nélkül
						max.magassag=magassag;
						max.utolso_merete=utolso_merete;
					}
			if (utolso_merete>=meret[k]) {//A k-adikat olyan toronyra tehetjük, ahol nagyobb kocka van legfelül.
					if ((magassag+meret[k])>max.magassag){
						max.magassag=magassag+meret[k];
						max.utolso_merete=meret[k];
					}
			}
		}
	return max;
	}
	public static void main(String[] args){
		int n,i;
		n=suly.length-1;
		System.out.println( "Toronyepites - rekurziv programozassal");
		System.out.println("A feladat adatai:");
		System.out.println("Kockak szama:"+(n+1));
							System.out.print("     Kockak : ");
		for (i=1;i<=n+1;i++) System.out.print(i+" ");
							System.out.println();
							System.out.print("     sulyok : ");
		for (i=0;i<=n;i++) 	System.out.print(suly[i]+" ");
							System.out.println();
							System.out.print("    meretek : ");
		for (i=0;i<=n;i++) 	System.out.print(meret[i]+" ");
							System.out.println();
		rendez(n);
		System.out.println("A legnagyobb magassag "+ epit(n).magassag);
	}  
}