Knapsack problem in Ruby (Dynamic Programming)

knapsack_problem_dp_in_ruby.md

Maximum Amount of Gold

Problem Introduction

You are given a set of bars of gold and your goal is to take as much gold as possible into your bag. There is just one copy of each bar and for each bar you can either take it or not (hence you cannot take a fraction of a bar).

Problem Description

Task.

Given 𝑛 gold bars, find the maximum weight of gold that fits into a bag of capacity 𝑊.

Input Format.

The first line of the input contains the capacity 𝑊 of a knapsack and the number 𝑛 of bars of gold. The next line contains 𝑛 integers 𝑤0,𝑤1, . . . ,𝑤𝑛−1 defining the weights of the bars of gold.

Constraints.

1 ≤ 𝑊 ≤ 104; 1 ≤ 𝑛 ≤ 300; 0 ≤ 𝑤0, . . . ,𝑤𝑛−1 ≤ 105.

Output Format.

Output the maximum weight of gold that fits into a knapsack of capacity 𝑊.

capacity_and_number = gets.chomp.split
bars_str = gets.chomp.split

capacity = capacity_and_number[0].to_i
number = capacity_and_number[1].to_i
bars = bars_str.map{|e| e.to_i}

previous_iteration = []
results = {}

bars.each do |bar|
  for weight in 0..capacity do
    previous_result = results[weight]

    if bar <= weight
      previous_max = previous_iteration.last[weight - bar] unless previous_iteration.empty?

      if previous_result
        if previous_max + bar <= previous_result
          results[weight] = previous_result
        elsif previous_max + bar <= weight
          results[weight] = previous_max + bar
        elsif previous_max + bar >= weight
          results[weight] = previous_result
        end
      else
        results[weight] = bar
      end
    else
      results[weight] = previous_result ? previous_result : 0
    end
  end
  previous_iteration << results.dup
end

puts results.values.max