Opus5
Class ZeroOneKnapsackProblem.Node

java.lang.Object
  |
  +--Opus5.AbstractObject
        |
        +--Opus5.ZeroOneKnapsackProblem.Node

All Implemented Interfaces:

java.lang.Cloneable, Comparable, Solution

Enclosing class:

ZeroOneKnapsackProblem

protected final class ZeroOneKnapsackProblem.Node

extends AbstractObject

implements Solution

Field Summary

protected int	numberPlaced The number of items considered.
protected int	totalProfit The current total profit.
protected int	totalWeight The current total weight.
protected int	unplacedProfit The sum of the profits of the items not yet considered.
protected int[]	x Indicates which items are taken.

Fields inherited from interface Opus5.Solution

copyright

Constructor Summary

ZeroOneKnapsackProblem.Node()
Constructs the root node in the solution space of this 0/1 knapsack problem.

ZeroOneKnapsackProblem.Node(ZeroOneKnapsackProblem.Node node)
Copy constructor.

Method Summary

java.lang.Object	clone() Clones this object.
protected int	compareTo(Comparable arg) Compares this node in the solution space with the specified comparable object.
int	getBound() Returns a lower bound on the objective function for this node and all possible descendants of this node in the solution space.
int	getObjective() Returns the value of the objective function for this node.
Enumeration	getSuccessors() Returns a enumeration that enumerates all the successors of this node in the solution space.
boolean	isComplete() Tests if this node is a complete solution.
boolean	isFeasible() Tests if this node is a feasible solution.
void	placeNext(int value) Places the next item into the knapsack if value is one.
java.lang.String	toString() Returns a string representation of this node of the solutions space.

Methods inherited from class Opus5.AbstractObject

compare, equals, isEQ, isGE, isGT, isLE, isLT, isNE

Methods inherited from class java.lang.Object

finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Methods inherited from interface Opus5.Comparable

compare, isEQ, isGE, isGT, isLE, isLT, isNE

Field Detail

totalProfit

protected int totalProfit

The current total profit.

totalWeight

protected int totalWeight

The current total weight.

unplacedProfit

protected int unplacedProfit

The sum of the profits of the items not yet considered.

numberPlaced

protected int numberPlaced

The number of items considered.

x

protected int[] x

Indicates which items are taken.

Constructor Detail

ZeroOneKnapsackProblem.Node

public ZeroOneKnapsackProblem.Node()

Constructs the root node in the solution space of this 0/1 knapsack problem.

ZeroOneKnapsackProblem.Node

public ZeroOneKnapsackProblem.Node(ZeroOneKnapsackProblem.Node node)

Copy constructor. Constructs a node in the solution space of this 0/1 knapsack problem by copying the values of a given node.

Parameters:

node - The given node.

Method Detail

clone

public java.lang.Object clone()

Clones this object.

Overrides:

clone in class java.lang.Object

Returns:

A clone of this object.

getObjective

public int getObjective()

Returns the value of the objective function for this node. The result is just -totalProfit

Specified by:

getObjective in interface Solution

Returns:

The value of the objective function.

getBound

public int getBound()

Returns a lower bound on the objective function for this node and all possible descendants of this node in the solution space. The reusult is just -(totalProfit+unplacedProfit).

Specified by:

getBound in interface Solution

Returns:

A lower bound on the object function.

isFeasible

public boolean isFeasible()

Tests if this node is a feasible solution.

Specified by:

isFeasible in interface Solution

Returns:

True if the total weight selected is less or equal to the capacity of this knapsack; false otherwise.

isComplete

public boolean isComplete()

Tests if this node is a complete solution.

Specified by:

isComplete in interface Solution

Returns:

True if all the items have been considered; false otherwise.

placeNext

public void placeNext(int value)

Places the next item into the knapsack if value is one.

Parameters:

value - Indicates whether to place the next item into the knapsack.

toString

public java.lang.String toString()

Returns a string representation of this node of the solutions space.

Overrides:

toString in class java.lang.Object

Returns:

A string representation of this node of the solutions space.

getSuccessors

public Enumeration getSuccessors()

Returns a enumeration that enumerates all the successors of this node in the solution space.

Specified by:

getSuccessors in interface Solution

Returns:

An enumeration that enumerates the successors of this node.

See Also:

Enumeration

compareTo

protected int compareTo(Comparable arg)

Compares this node in the solution space with the specified comparable object. This method is not implemented.

Overrides:

compareTo in class AbstractObject

Throws:

MethodNotImplemented - Always.