public interface

KnapsackSolver

org.apache.helix.controller.strategy.knapsack.KnapsackSolver
Known Indirect Subclasses

Class Overview

Interface for a factory of multidimensional 0-1 knapsack solvers that support reductions

Based on the C++ knapsack solver in Google's or-tools package.

Summary

Nested Classes
enum KnapsackSolver.SolverType Collection of supported algorithms  
Public Methods
abstract boolean bestSolutionContains(int itemId)
Check if an element was selected in the optimal solution
abstract String getName()
Get the name of this solver
abstract void init(ArrayList<Long> profits, ArrayList<ArrayList<Long>> weights, ArrayList<Long> capacities)
Initialize the solver
abstract void setUseReduction(boolean useReduction)
Set whether a reduction should be used to prune paths early on
abstract long solve()
Solve the knapsack problem
abstract boolean useReduction()
Check if a reduction should be used to prune paths early on

Public Methods

public abstract boolean bestSolutionContains (int itemId)

Check if an element was selected in the optimal solution

Parameters
itemId the index of the element to check
Returns
  • true if the item is present, false otherwise

public abstract String getName ()

Get the name of this solver

Returns
  • solver name

public abstract void init (ArrayList<Long> profits, ArrayList<ArrayList<Long>> weights, ArrayList<Long> capacities)

Initialize the solver

Parameters
profits profit for each element if selected
weights cost of each element in each dimension
capacities maximum total weight in each dimension

public abstract void setUseReduction (boolean useReduction)

Set whether a reduction should be used to prune paths early on

Parameters
useReduction true to enable, false to disable

public abstract long solve ()

Solve the knapsack problem

Returns
  • the approximated optimal weight

public abstract boolean useReduction ()

Check if a reduction should be used to prune paths early on

Returns
  • true if reduction enabled, false otherwise