import java.io.*;
import java.util.*;
import java.util.Arrays;
import org.chocosolver.solver.Model;
import org.chocosolver.solver.Solver;
import org.chocosolver.solver.variables.IntVar;
import org.chocosolver.solver.constraints.IIntConstraintFactory.*;
import org.chocosolver.solver.search.strategy.Search;

public class AllocateBP {

    Person person[];       // the employees to be allocated to cost centres
    int salary[];          // salary[i] of ith person
    Model model;           // the model
    Solver solver;         // the solver object
    IntVar employee[];     // employee[i] = j <-> ith employee is in cost centre j
    IntVar costCentre[];   // sum of salaries in cost centre
    int budget;            // the budget for each cost centre
    int n;                 // number of employees
    int m;                 // number of cost centres
    String id;             // an identification for the problem
	
    public AllocateBP(String fname,int numberOfPeople,int numberOfCostCentres,int budget) throws Exception {
	n            = numberOfPeople;
	m            = numberOfCostCentres;
	this.budget  = budget;
	id           = fname;
	person       = new Person[n];
	salary       = new int[n];
	model        = new Model(id);
	solver       = model.getSolver();
	employee     = model.intVarArray("employee",n,0,m-1);
	costCentre   = model.intVarArray("cost centre",m,0,budget);
	

	Scanner sc = new Scanner(new File(fname));
	for (int i=0;i<n;i++) person[i] = new Person(sc.next(),sc.nextInt());
	sc.close();

	for (int i=0;i<n;i++) salary[i] = person[i].salary;

	model.binPacking(employee,salary,costCentre,0).post();
    }
    
    // solve using value ordering over decision variables
    boolean solve(){
	solver.setSearch(Search.minDomUBSearch(employee));
	return solver.solve();
    }
    
    public String toString(){
	String s = id + " " + " #employees: " + n + 
	          " #centres: " + m + " budget: " + budget + "\n";
	for (int i=0;i<m;i++){
	    s = s + "centre-"+ i +": ";
	    for (int j=0;j<n;j++)
		if (employee[j].getValue() == i) s = s + person[j] +" ";
	    s = s + " ... cost: "+ costCentre[i].getValue() +"\n";
	}	
	return s;
    }

    public static void main(String[] args) throws FileNotFoundException, IOException, Exception {
	if (args.length == 0){
	    System.out.println("java AllocateBP fname budget #employees #centres");
	    return;
	}
	String fname          = args[0];
	int budget            = Integer.parseInt(args[1]);
	int numberOfEmployees = Integer.parseInt(args[2]);    
	int numberOfCentres   = Integer.parseInt(args[3]);

	AllocateBP alloc = new AllocateBP(fname,numberOfEmployees,numberOfCentres,budget);
	boolean solved = alloc.solve(); 
	System.out.println(solved);
	if (solved) System.out.println(alloc);
	System.out.println("nodes: " + alloc.solver.getMeasures().getNodeCount() +
			   "   cpu: " + alloc.solver.getMeasures().getTimeCount());
    }
}