Module: JobInterview::Knapsack

Included in:
Answer
Defined in:
lib/job_interview/knapsack.rb

Instance Method Summary collapse

Instance Method Details

#knapsack(items, capacity, algorithm = :dynamic) ⇒ Object

Given a set of items, each with a weight and a value, determines the maximum profit you can have while keeping the overall weight smaller than the capacity of the knapsack.

Parameters:

  • items (Array<Array>) —

    An array of pairs (weight, profit) representing the items

  • capacity (Integer) —

    The capacity of the knapsack

  • algorithm (:memoize, :dynamic) (defaults to: :dynamic) —

    The algorithm used to solve this, defaults to :dynamic



12
13
14
15
16
17
18
 
# File 'lib/job_interview/knapsack.rb', line 12

def knapsack(items, capacity, algorithm = :dynamic)
  if algorithm == :memoize
    knapsack_memoize(items, capacity)
  elsif algorithm == :dynamic
    knapsack_dynamic_programming(items, capacity)
  end
end