knapsack

Solutions to knapsack problem variations.

Currently, only solutions for knapsack 0/1 are available.

Knapsack 0/1

Contains the following solutions:

• Deterministic Recursive

  Time Complexity  : O( 2(Number of items) )
  Space Complexity : O( (Number of items)*(Recursive function frame size) )
  

• Deterministic Recursive with 2D buffer

  Time Complexity  : O( (Number of items)*(Total knapsack space) )
  Space Complexity : O( (Number of items)*(Total knapsack space) )
  

• Deterministic Iterative with 2D buffer

  Time Complexity  : O( (Number of items)*(Total knapsack space) )
  Space Complexity : O( (Number of items)*(Total knapsack space) )
  

• Deterministic Iterative with 1D buffer

  Time Complexity  : O( (Number of items)*(Total knapsack space) )
  Space Complexity : O( (Total knapsack space) )
  

• Stochastic with Simulated Annealing

  Time Complexity  : O( (Number of iterations in Simulated Annealing) )
  Space Complexity : O( (Number of bits needed to store the state of included items) )