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, tracequeueIndex| 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, watchedVariableGroundedauxiliaryVariables, checkInput, checkInput, checkInputForDuplication, checkInputForDuplicationSkipSingletons, checkInputForNullness, checkInputForNullness, checkInputForNullness, derivative, getDubletonsSkipSingletons, imposeDecompositionpublic 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()
ConstraintcleanAfterFailure in class Constraintpublic void removeLevelLate(int level)
RemoveLevelLateremoveLevelLate in interface RemoveLevelLatelevel - the level which is being removed.public void consistency(Store store)
Constraintconsistency in class Constraintstore - constraint store within which the constraint consistency is being checked.public void impose(Store store)
Constraintimpose in class Constraintstore - the constraint store to which the constraint is imposed to.public void queueVariable(int level,
Var v)
ConstraintqueueVariable in class Constraintlevel - the level of the store at which the change has occurred.v - variable which has changed.public int numberArgs()
ConstraintnumberArgs in class Constraintpublic int getDefaultConsistencyPruningEvent()
getDefaultConsistencyPruningEvent in class Constraintpublic boolean satisfied()
SatisfiedPresentImplementations 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 SatisfiedPresentpublic String toString()
ConstrainttoString in class ConstraintCopyright © 2022. All rights reserved.