import java.util.* ;
import java.math.*;

class Liste extends ArrayList<Integer>{}

class Solution{
    public ArrayList<Integer> l1;
    public ArrayList<Integer> l2;
    public int val;

    public Solution(ArrayList<Integer> ll1,ArrayList<Integer> ll2, int v){
	l1 = ll1;
	l2 = ll2;
	val = v;
    }

    public Solution(Solution s){
	l1 = new ArrayList<Integer>(s.l1);
	l2 = new ArrayList<Integer>(s.l2);
	val = s.val;
    }
    
    public String toString(){
	return "l1 : " + l1 + "l2 : " + l2 + "val " + val;
    }
    
}

class Exo2{

    public static int sommeTab(int[] t){
	int S = 0;
	for(int i=0;i<t.length;i++){
	    S = S + t[i];
	}
	return S;
    }


    
    /////////////////////////////////////////////////////////////////////////////////
    //////// versions qui retournent une solution
    /////////////////////////////////////////////////////////////////////////////////
   public static Solution P2CMAXclientSolDP(int []t){
	int S = sommeTab(t);
	int n = t.length;
	Solution [][][] mem = new Solution[n+1][S+1][S+1];
	for(int i = 0;i< n+1;i++){
	    for(int j = 0;j< S+1;j++){
		for(int k = 0;k< S+1;k++){
		    mem[i][j][k]=null;
		}
	    }
	}
	return P2CMAXAUXSolDP(mem, t,0,0,0);
    }


    
    public static Solution P2CMAXAUXSolDP(Solution[][][]mem, int[] t,int i, int load1, int load2){
	//0 <= i <= t.length
	//0 <= load1 <= S
	//0 <= load2 <= S
	//makespan min pour ordonnancer t[i..t.length-1] sur 2 machines ayant chacune un load i
	if(mem[i][load1][load2]==null){
	    Solution res = null;
	    if(i==t.length){
		res= new Solution(new ArrayList<Integer>(),new ArrayList<Integer>(),Math.max(load1,load2));
	    }
	    else{
		Solution res1= P2CMAXAUXSolDP(mem,t,i+1,load1+t[i],load2);
		Solution res2= P2CMAXAUXSolDP(mem,t,i+1,load1,load2+t[i]);
		if(res1.val < res2.val){		    
		    res = new Solution(res1); //il faut copier en profondeur
		    res.l1.add(i);
		}
		else{
		    res = new Solution(res2);
		    res.l2.add(i);
		}
	    }
	    mem[i][load1][load2]=res;
	}
	return mem[i][load1][load2];
    }

    
    /////////////////////////////////////////////////////////////////////////////////
    //////// versions qui retournent la valeur opt
    /////////////////////////////////////////////////////////////////////////////////

    
    public static int P2CMAXclientValDP(int []t){
	int S = sommeTab(t);
	int n = t.length;
	int [][][] mem = new int[n+1][S+1][S+1];
	for(int i = 0;i< n+1;i++){
	    for(int j = 0;j< S+1;j++){
		for(int k = 0;k< S+1;k++){
		    mem[i][j][k]=-1;
		}
	    }
	}
	return P2CMAXAUXValDP(mem, t,0,0,0);
    }


    
    public static int P2CMAXAUXValDP(int[][][]mem, int[] t,int i, int load1, int load2){
	//0 <= i <= t.length
	//0 <= load1 <= S
	//0 <= load2 <= S
	//makespan min pour ordonnancer t[i..t.length-1] sur 2 machines ayant chacune un load i
	if(mem[i][load1][load2]==-1){
	    int res=0;
	    if(i==t.length){
		res= Math.max(load1,load2);
	    }
	    else{
		res= Math.min(P2CMAXAUXValDP(mem,t,i+1,load1+t[i],load2),P2CMAXAUXValDP(mem,t,i+1,load1,load2+t[i]));
	    }
	    mem[i][load1][load2]=res;
	}
	return mem[i][load1][load2];
    }
    
    
    
    public static int P2CMAXAUXVal(int[] t,int i, int load1, int load2){
	//0 <= i <= t.length
	//makespan min pour ordonnancer t[i..t.length-1] sur 2 machines ayant chacune un load i
	if(i==t.length){
	    return Math.max(load1,load2);
	}
	else{
	    return Math.min(P2CMAXAUXVal(t,i+1,load1+t[i],load2),P2CMAXAUXVal(t,i+1,load1,load2+t[i]));
	   
	}
   }
    
 

    public static void main(String[]args){
	int[]jobs = {10,2,2,20,5,4,10,2,2,20,5,4,10,2,2,12,5,4,10,2,2,20,5,4,2,20,5,4,2,2,5,2,2,5,2,2,5,2,2,5,2,2,5,2,2,5,2,2,5};
	System.out.println("main pour constater que sans DP c'est exponentiel, vs O(nS^2) (si les 2 versions sont rapides, rajouter quelques jobs en plus ...)");
	//	System.out.println("p2cmaxclient (retourne solution ET DP) " + P2CMAXclient(jobs));
	//System.out.println("P2CMAXAUXVal (retourne int et pas DP) " + P2CMAXAUXVal(jobs,0,0,0));
	System.out.println("P2CMAXclientValDP (retourne int et DP) " + P2CMAXclientValDP(jobs));
	
    }
    
}