Package org.ddolib.examples.knapsack

Class KSAlgo

java.lang.Object

org.ddolib.examples.knapsack.KSAlgo

public class KSAlgo
extends Object

Utility class providing algorithms to solve the Knapsack Problem.

Constructor Summary

Constructors

Constructor	Description
KSAlgo()

Method Summary

Modifier and Type	Method	Description
static int	greedyKS(KSProblem problem)	Provides a greedy approximation for the Knapsack Problem.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

KSAlgo

public KSAlgo()

Method Details

greedyKS

public static int greedyKS(KSProblem problem)

Provides a greedy approximation for the Knapsack Problem.

The algorithm sorts items in descending order of their profit-to-weight ratio (profit / weight) and selects items sequentially as long as they fit within the remaining capacity.

Parameters:

problem - the Knapsack Problem instance to solve

Returns:

the total profit of the selected items, providing a primal bound (lower bound) on the optimal solution