public class Knapsack extends Constraint implements UsesQueueVariable, SatisfiedPresent, RemoveLevelLate
Tha major extensions of that paper are the following. The quantity variables do not have to be binary. The profit and capacity of the knapsacks do not have to be integers. In both cases, the constraint accepts any finite domain variable.
This implementation is based on the implementation obtained by Wadeck Follonier during his work on a student semester project.
We would like to thank Meinolf Sellmann for his appreciation of our work and useful comments.
Modifier and Type  Field and Description 

int 
currentLevel
It specifies the current level of the constraint store at which
the consistency function of this constraint is being executed.

static boolean 
debugAll
It specifies if any debugging information should be printed.

KnapsackItem[] 
items
The array of items present in the knapsack constraint.

protected IntVar 
knapsackCapacity
This is a finite domain variable to specify the knapsack capacity.

protected IntVar 
knapsackProfit
This is a finite domain variable to specify the knapsack profit.

Tree 
tree
The tree for the storing information about the maximalWeight,
sum of weights and sum of profits.

atomicExecution, consistencyPruningEvents, constraintScope, earlyTerminationOK, increaseWeight, numberId, scope, trace
queueIndex
Constructor and Description 

Knapsack(int[] profits,
int[] weights,
IntVar[] quantity,
IntVar knapsackCapacity,
IntVar knapsackProfit)
It constructs the knapsack constraint.

Knapsack(KnapsackItem[] items,
IntVar knapsackCapacity,
IntVar knapsackProfit)
It constructs an knapsack constraint.

Modifier and Type  Method and Description 

void 
cleanAfterFailure()
It is executed after the constraint has failed.

void 
consistency(Store store)
It is a (most probably incomplete) consistency function which removes the
values from variables domains.

int 
getDefaultConsistencyPruningEvent() 
void 
impose(Store store)
It imposes the constraint in a given store.

int 
numberArgs()
It returns the number of variables within a constraint scope.

void 
queueVariable(int level,
Var v)
This is a function called to indicate which variable in a scope of
constraint has changed.

void 
removeLevelLate(int level)
This function is called in case of the backtrack.

boolean 
satisfied()
It checks if the constraint is satisfied.

String 
toString()
It produces a string representation of a constraint state.

afc, arguments, decompose, getConsistencyPruningEvent, getGuideConstraint, getGuideValue, getGuideVariable, grounded, grounded, id, impose, imposeDecomposition, increaseWeight, intArrayToString, long2int, removeConstraint, requiresMonotonicity, setConsistencyPruningEvent, setConstraintScope, setScope, setScope, setScope, setScope, setScope, setWatchedVariableGrounded, supplyGuideFeedback, updateAFC, watchedVariableGrounded
auxiliaryVariables, checkInput, checkInput, checkInputForDuplication, checkInputForDuplicationSkipSingletons, checkInputForNullness, checkInputForNullness, checkInputForNullness, derivative, getDubletonsSkipSingletons, imposeDecomposition
public static final boolean debugAll
protected IntVar knapsackCapacity
protected IntVar knapsackProfit
public int currentLevel
public Tree tree
public KnapsackItem[] items
public Knapsack(KnapsackItem[] items, IntVar knapsackCapacity, IntVar knapsackProfit)
items
 list of items in knapsack with its weight, profit and quantity variable.knapsackCapacity
 overall knapsack capacity.knapsackProfit
 overall profit obtained by the items in the knapsack.public Knapsack(int[] profits, int[] weights, IntVar[] quantity, IntVar knapsackCapacity, IntVar knapsackProfit)
profits
 the list of profits, each for the corresponding item no.weights
 the list of weights, each for the corresponding item no.quantity
 finite domain variable specifying allowed values for the vars.knapsackCapacity
 finite domain variable specifying the capacity limit of the knapsack.knapsackProfit
 finite domain variable defining the profitpublic void cleanAfterFailure()
Constraint
cleanAfterFailure
in class Constraint
public void removeLevelLate(int level)
RemoveLevelLate
removeLevelLate
in interface RemoveLevelLate
level
 the level which is being removed.public void consistency(Store store)
Constraint
consistency
in class Constraint
store
 constraint store within which the constraint consistency is being checked.public void impose(Store store)
Constraint
impose
in class Constraint
store
 the constraint store to which the constraint is imposed to.public void queueVariable(int level, Var v)
Constraint
queueVariable
in class Constraint
level
 the level of the store at which the change has occurred.v
 variable which has changed.public int numberArgs()
Constraint
numberArgs
in class Constraint
public int getDefaultConsistencyPruningEvent()
getDefaultConsistencyPruningEvent
in class Constraint
public boolean satisfied()
SatisfiedPresent
Implementations of this interface for constraints that are not PrimitiveConstraint may require constraint imposition and consistency check as a requirement to work correctly.
satisfied
in interface SatisfiedPresent
public String toString()
Constraint
toString
in class Constraint
Copyright © 2022. All rights reserved.