/*
 * For more information about this file, see 
 * "Choco: Constraint Programming i Java"
 * http://www.hakank.org/webblogg/archives/001113.html
 *
 *
 * Problem from http://sourceforge.net/forum/forum.php?thread_id=1432186&forum_id=335511
 * The code was slighly changed by hakank.
 
 * Knapsack maximization problem example 
 * @author Fernando Lopez Hernandez (f.lopezATuamDOTes) 
 * 
 * In this problem a thief have a knapsack with capacity of 10 units. 
 * He could charge the knapsack with golden ingots of size 4, silver ingots 
 * of size 3, and bronze ingots of size 2. Each ingot value is 15, 12 and 7 
 * respectively. 
 * 
 * The solver goal is to find a solution who maximize profit with the above 
 * restrictions. That is to say: If G represents the number of golden ingots, 
 * S the number of silver ingots, B the number of bronze ingots, 
 * and P the profit, we define the following constraints: 
 * 4G + 3S + 2B <= 10 
 * 15G + 12S + 7B = P 
 * 
 */ 

import choco.*; 
import choco.integer.*; 
 
class Knapsack 
{ 
  public static void main(String[] args) { 

    int capacity = 10; // ca
    
    // Define the problem 
    Problem pb = new Problem(); 
    
    // Define the variables 
    IntDomainVar g = pb.makeBoundIntVar("G",0,10); // gold
    IntDomainVar s = pb.makeBoundIntVar("S",0,10); // silver
    IntDomainVar b = pb.makeBoundIntVar("B",0,10); // bronze
    IntDomainVar p = pb.makeBoundIntVar("P",0,1000); 
    
    // Define the constraints 
    pb.post(pb.leq(pb.scalar(new int[]{4,3,2},new IntVar[]{g,s,b}),capacity)); 
    pb.post(pb.eq(pb.scalar(new int[]{15,12,7},new IntVar[]{g,s,b}),p)); 
    
    // Solve the problem maximizing profit 
    pb.maximize(p,false); 
    
    System.out.println("Solution: Golden (size 4)="+ g.getVal()+
                       " Silver (size 3)=" + s.getVal()+ 
                       " Bronze (size 2)="+b.getVal() + 
                       " P: " + p.getVal() + " Capacity: " + capacity ); 
  } 
} 


/*
The execution of the program:
 
  $ java Knapsack 
  Solution: Golden (size 4) = 1 Silver (size 3) = 2 Bronze (size 2) = 0 P: 39 Capacity: 10

*/