/*
* Copyright 2002, 2003, 2004, 2005 - <A href="http://www.koalog.com">Koalog</A>
*/
package com.koalog.jcs.examples;
import org.apache.log4j.PropertyConfigurator;
import com.koalog.jcs.variable.IntegerVariable;
import com.koalog.jcs.variable.BooleanVariable;
import com.koalog.jcs.constraint.BaseProblem;
import com.koalog.jcs.constraint.arithmetic.Mul;
import com.koalog.jcs.constraint.arithmetic.Sum;
import com.koalog.jcs.constraint.arithmetic.SmallerSum;
/**
* This is the famous Knapsack problem.
* Given:
* <ul>
* <li>n objects of given volumes and weights,</li>
* <li>a bag of a given capacity (volume),</li>
* it consists in putting in the bag as much weight as possible.
* </ul>
*
* @author Yan Georget
*/
public class KnapsackProblem extends BaseProblem {
//------------------------------------------------------------------------
// PROPERTIES
//------------------------------------------------------------------------
IntegerVariable weight;
//------------------------------------------------------------------------
// CONSTRUCTORS
//------------------------------------------------------------------------
/**
* Sole constructor.
* @param volumes the volumes
* @param weights the weights
* @param capacity the capacity
*/
public KnapsackProblem(int[] volumes, int[] weights, int capacity) {
int n = volumes.length;
BooleanVariable[] b = new BooleanVariable[n];
IntegerVariable[] v = new IntegerVariable[n];
IntegerVariable[] w = new IntegerVariable[n];
for (int i=0; i<n; i++) {
b[i] = new BooleanVariable("b" + i);
v[i] = new IntegerVariable("v" + i);
w[i] = new IntegerVariable("w" + i);
add(new Mul(v[i], volumes[i], b[i]));
add(new Mul(w[i], weights[i], b[i]));
}
weight = new IntegerVariable("weight");
add(new Sum(weight, w));
add(new SmallerSum(v, capacity+1));
setVariables(b);
}
//------------------------------------------------------------------------
// STATIC METHODS
//------------------------------------------------------------------------
/**
* Runs the problem.
* @param args the command line arguments:
* args[0] must contain a log4j properties file location
*/
public static void main(String args[]) {
PropertyConfigurator.configure(args[0]);
int[] volumes = new int[] {
40,40,38,38,36,36,34,34,32,32,30,30,28,28,26,26,24,24,22,22
};
int[] weights = new int[] {
40,40,38,38,36,36,34,34,32,32,30,30,28,28,26,26,24,24,22,22
};
new KnapsackMaximizer(new KnapsackProblem(volumes,
weights,
55)).optimize();
}
}
|