//
//
import java.io.*;

import static choco.Choco.*;
import choco.cp.model.CPModel;
import choco.cp.solver.CPSolver;
import choco.kernel.model.Model;
import choco.cp.solver.search.integer.varselector.MinDomain;
import choco.cp.solver.search.integer.varselector.StaticVarOrder;
import choco.cp.solver.search.integer.valiterator.IncreasingDomain;
import choco.cp.solver.search.integer.valiterator.DecreasingDomain;
import choco.kernel.solver.Solver;
import choco.kernel.model.variables.integer.IntegerExpressionVariable;
import choco.kernel.model.variables.integer.IntegerVariable;

public class OptimizeV2 {

  
  public static void main(String[] args) throws FileNotFoundException, IOException {
      MyIo fin            = new MyIo(args[0]);
      int n               = fin.getNextInt(); // number of numbers
      Model m             = new CPModel();
      IntegerVariable D[] = new IntegerVariable[n];
      int w[]             = new int[n];
      int tot             = 0;                // sum of w[i]
      for (int i=0;i<n;i++){
	  w[i] = fin.getNextInt();
	  D[i] = makeIntVar("D[" + i + "]",0,1);
	  tot  = tot + w[i];
      }

      fin.close();
      
      IntegerVariable sumR = makeIntVar("sumR",0,tot/2); // half the sum of weights
      m.addConstraint(eq(sumR,scalar(w,D)));  // sumR is sum of weights on the right         

      Solver s = new CPSolver(); 
      s.read(m); 
      s.setVarIntSelector(new StaticVarOrder(s.getVar(D)));
      s.maximize(s.getVar(sumR),false);                    // maximize the sum on the right
      s.printRuntimeSatistics();
      System.out.println("feasible: " + s.isFeasible());

      int wl = 0, wr = 0; // weight left and right

      if (s.isFeasible()){
	  for (int i=0;i<n;i++){
	      System.out.print(w[i] + ":" + s.getVar(D[i]).getVal() + " ");
	      if (s.getVar(D[i]).getVal() == 0)
		  wl = wl + w[i];
	      else wr = wr + w[i];
	  }	  
	  System.out.println();
	  System.out.println("wl = " + wl + "  wr = " + wr);
      }

  }
}
//
// Questions
// (0) NOTE: no L or R variables! Less constraints too!
// (1) We now MAXIMIZE the sum of weights on the right, to be as near to tot/2 as possible
// (2) Can we put a limit on search, i.e sacrafice completeness?
//      hint: s.setNodeLimit(2000);
// (3) Is there a better, smarter way to solve this problem?
//      hint: the KK heuristic
//