import java.io.*;
import java.util.*;
import java.util.Arrays;
import java.util.Collections;
import org.chocosolver.solver.*;
import org.chocosolver.solver.variables.*;
import org.chocosolver.solver.constraints.*;
import org.chocosolver.solver.search.strategy.*;

public class BinPack {

    private int[] data;         // the data to be packed
    private Solver solver;      // a solver object, to attach variables and constraints
    private IntVar inBin[][];   // inBin[i][j] = 1 iff jth number is in ith bin
    private IntVar inBinT[][];  // transpose of inBin[i][j], used for summing columns!
    private IntVar load[];      // load[i] is sum of the numbers in ith bin
    private IntVar binUsed[];   // binUsed[i] = 1 iff load[i] > 0
    private IntVar totBinsUsed; // total number of bins used
    private int c;              // the capacity of each bin
    private int n;              // number of items to pack
    private int m;              // number of bins you have
    private String id;          // an identification for the problem
	
    public BinPack(String fname,int numberOfItems,int numberOfBins,int capacity) throws Exception {
	n              = numberOfItems;
	m              = numberOfBins;
	c              = capacity;
	id             = fname;
	data           = new int[n];
	solver         = new Solver(id);
	inBin          = VF.enumeratedMatrix("inBin",m,n,0,1,solver);
	inBinT         = new IntVar[n][m];	
	load           = VF.enumeratedArray("load",m,0,c,solver);
	binUsed        = VF.enumeratedArray("binUsed",m,0,1,solver);
	totBinsUsed    = VF.enumerated("totBinsUsed",0,m,solver);

	for (int i=0;i<m;i++)
	    for (int j=0;j<n;j++)
		inBinT[j][i] = inBin[i][j];
	//
	// load up transpose inBinT from inBin
	//

	Scanner sc = new Scanner(new File(fname));
	for (int j=0;j<n;j++) data[j] = sc.nextInt();
	sc.close();

	// EDIT
	Arrays.sort(data);
	reverse(data,0,n-1);
	//
	// first fit decreasing
	//

	for (int i=0;i<m;i++)
	    solver.post(ICF.scalar(inBin[i],data,load[i]));
	// 
	// constrain load[i] to be the scalar product of inBin[i] and data[i]
	//

	for (int i=0;i<m;i++){
	    Constraint c1 = ICF.arithm(load[i],">",0);
	    Constraint c2 = ICF.arithm(binUsed[i],"=",1);
	    LCF.ifThen(c1,c2);
	    LCF.ifThen(c2,c1);
	}
	// 
	// constrain binUsed[i] to be 1 if and only if there are some
	// items stacked in the ith bin, i.e. load[i] > 0
	//

	IntVar ONE = VF.fixed("one",1,solver);
	for (int i=0;i<n;i++)
	    solver.post(ICF.sum(inBinT[i],"=",ONE));
	//
	// constrain a piece of data such that it can only be in one bin at a time!
	// i.e. the sum of a column of the array inBin (row of inBinT[i]) must be equal 
	//      to 1, such that an item/number is in exactly one bin
	// NOTE: inBinT is transpose of inBin
	//

	solver.post(ICF.sum(binUsed,"=",totBinsUsed));
	//
	// constrain totBinsUsed to be the sum of the binUsed vector
	// we now need to minimise this value
	//

	// EDIT
	// for (int i=0;i<m-1;i++)
	//   solver.post(ICF.arithm(load[i],">=",load[i+1]));
	//
	// symmetry breaking consistent with first fit decreasing
	// heaviest bins are low index
	//

	// EDIT
	//for (int i=0;i<m-1;i++)
	//  solver.post(ICF.lex_less(inBin[i],inBin[i+1]));
	//
	// symmetry breaking such that inBin[i] lex< inBin[i+1]
	//
    }

    public void swap(int[] a,int i,int j){
	int temp = a[i]; a[i] = a[j]; a[j] = temp;
    }

    public void reverse(int[] a,int lwb,int upb){
	if (lwb<upb){
	    swap(a,lwb,upb);
	    reverse(a,lwb+1,upb-1);
	}
    }

    public Solver getSolver(){return solver;}

    public IntVar getTotalBinsUsed(){return totBinsUsed;}

    public IntVar[] getDecisionVars(){
	IntVar D[] = new IntVar[m * n];
	for (int i=0,k=0;i<m;i++)
	    for (int j=0;j<n;j++,k++){
		D[k] = inBin[i][j];
	    }
	return D;
    }

    public String toString(){
	String s = id + " " + " #items: " + n + 
	          " #bins: " + m + " capacity: " + c + "\n";
	s = s + "#bins used: " +  totBinsUsed.getValue() + "\n";
	int sum = 0;
	for (int j=0;j<n;j++){
	    s = s + data[j] + " ";
	    sum = sum + data[j];
	}
	s = s + "sum: " + sum + "\n";
	for (int i=0;i<m;i++){
	    s = s + "bin[" + i + "] ";
	    for (int j=0;j<n;j++)
		s = s + inBin[i][j].getValue() + " ";
	    s = s + load[i].getValue() + "\n";
	}
	return s;
    }


    public static void main(String[] args) throws FileNotFoundException, IOException, Exception {
	String fname       = args[0];
	int capacity       = Integer.parseInt(args[1]);
	int numberOfItems  = Integer.parseInt(args[2]);    
	int numberOfBins   = Integer.parseInt(args[3]);

	BinPack bp = new BinPack(fname,numberOfItems,numberOfBins,capacity);

	Solver solver = bp.getSolver();

	// EDIT
	// solver.set(ISF.lexico_LB(bp.getDecisionVars()));
	//
	// only consider the decision variables
	// 
	
	// EDIT
	solver.set(ISF.lexico_UB(bp.getDecisionVars()));
	//
	// select values 1 before 0 (why?)
	//
	System.out.println(solver.findSolution());	
	System.out.println(bp);
	System.out.println("nodes: " + solver.getMeasures().getNodeCount() + "   cpu: " + solver.getMeasures().getTimeCount());
    }
}