Package org.ddolib.examples.knapsack

package org.ddolib.examples.knapsack
This package implements the acs, astar and ddo models for the Knapsack Problem (KS). The Knapsack problem is a classic optimization problem where the goal is to maximize the total value of items while staying within a given weight limit. The dynamic programming model is used to solve this problem is using the recurrence relation: KS(i, c) = max(KS(i-1, c), KS(i-1, c - w[i]) + p[i]) where KS(i, c) is the maximum value of the first i items with a knapsack capacity of c, p[i] is the profit of item i, w[i] is the weight of item i.
  • Classes
    Class
    Description
    KSAcsMain
    Knapsack Problem (KS) with Acs.
    KSAlgo
    Utility class providing algorithms to solve the Knapsack Problem.
    KSAstarMain
    Knapsack Problem (KS) with AsTar.
    KSDdoMain
    Knapsack Problem (KS) with Ddo.
    KSDdoMainWithCluster
    Knapsack Problem (KS) with Ddo.
    KSDistance
    Distance measure for states in a Knapsack (KS) problem.
    KSDominance
    Dominance relation for the Knapsack Problem (KS).
    KSFastLowerBound
    Fast lower bound heuristic for the Knapsack Problem (KS).
    KSLnsMain
    Entry point for solving the 0/1 Knapsack Problem (KS) using a Large Neighborhood Search (LNS) approach combined with Decision Diagram Optimization (DDO).
    KSProblem
    Represents an instance of the Knapsack Problem (KS).
    KSRanking
    State ranking for the Knapsack Problem (KS).
    KSRelax
    Relaxation for the Knapsack Problem (KS).