My solution correctly solves the problem, but I would like to optimize its performance. For a capacity of 7 and bars = [ 4, 1, 1, 2, 1], the output is 7.

def knapsack(capacity, bars)
    if capacity == 0 || bars.nil? || bars[0].nil?
        return 0

    solutions = []
    sum = 0
    (1..capacity).each do |i|
        break if sum > capacity
        bars.combination(i).lazy.each do |comb|
            sum = comb.reduce(&:+)
            solutions << sum

    solutions.select{|i| i <= capacity}.max
  • 1
    \$\begingroup\$ Welcome to Code Review! I hope you get some good answers. \$\endgroup\$
    – Phrancis
    Jul 21, 2016 at 19:11
  • 1
    \$\begingroup\$ Just as a hint, you may want to look into solving the knapsack problem with dynamic programming. It's not hard and is much more performant, especially for large data sets. I can post an example solution later if you are interested. Your code as posted looks like well written ruby but your algorithm is a sub-optimal brute-force approach. \$\endgroup\$
    – Zack
    Jul 21, 2016 at 20:16


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.