Package org.ddolib.examples.boundedknapsack

Class BKSDominance

java.lang.Object
org.ddolib.examples.boundedknapsack.BKSDominance
All Implemented Interfaces:
Dominance<Integer>
public class BKSDominance extends Object implements Dominance<Integer>
Implementation of a dominance rule for the Bounded Knapsack (BKS) problem.

This class defines how two states (represented here by integer capacities) can dominate one another in the search space. In this context, a state with a smaller capacity is considered dominated by a state with a larger one, since it provides fewer remaining resources for future item selections.

The dominance mechanism helps prune the search space efficiently in dynamic programming or branch-and-bound algorithms.

Example:


 BKSDominance dominance = new BKSDominance();
 boolean result = dominance.isDominatedOrEqual(5, 10); // true, since 5 < 10
See Also:

  • Constructor Details

    • BKSDominance

      public BKSDominance()

  • Method Details

    • getKey

      public Integer getKey(Integer capa)
      Returns the dominance key for a given state.

      In this simplified implementation, all states share the same key (0), meaning that dominance comparisons are applied globally without grouping.

      Specified by:
      getKey in interface Dominance<Integer>
      Parameters:
      capa - The state or capacity value for which the key is requested.
      Returns:
      Always returns 0, indicating no partitioning by key.

    • isDominatedOrEqual

      public boolean isDominatedOrEqual(Integer capa1, Integer capa2)
      Checks whether one state (capacity) is dominated or equal to another.

      In this implementation, capa1 is considered dominated or equal to capa2 if it is strictly smaller.

      Specified by:
      isDominatedOrEqual in interface Dominance<Integer>
      Parameters:
      capa1 - The first capacity (potentially dominated).
      capa2 - The second capacity (potential dominator).
      Returns:
      true if capa1 <= capa2, false otherwise.