A simple dynamic programming problem.

knapsack_spec.rb

require 'spec_helper'

# An exercise drawn from Grokking Algorithms, chapter 9 (pg. 162)
# https://www.manning.com/books/grokking-algorithms

KNAPSACK_CAPACITY = 4

class Good
  attr_accessor :weight, :price, :kind
  def initialize(w, p, k)
    @weight = w
    @price = p
    @kind = k
  end
end

class Knapsack < Array
  def <<(e)
    fail "#{e} must be a Good to go in Knapsack" unless e.is_a? Good

    added_weight = e.weight
    current_weight = self.map(&:weight).reduce(0, :+)
    fail 'Knapsack overcapacity!' if current_weight + added_weight > KNAPSACK_CAPACITY

    super
  end
end

class Thief
  attr_accessor :knapsack

  def initialize
    @knapsack = Knapsack.new
  end

  def steal_optimally_from(house)
    self
  end
end

class House
  attr_accessor :posessions

  def initialize(p)
    @posessions = p
  end
end

describe 'a Thief in the night' do
  let(:guitar) { Good.new(1,15,'guitar') }
  let(:stereo) { Good.new(4,30,'stereo') }
  let(:laptop) { Good.new(3,20,'laptop') }
  
  let(:house) { House.new([guitar, stereo, laptop]) }
  let(:house_with_iphone) { House.new([guitar, stereo, laptop, iphone]) }
  
  let(:thief) { Thief.new }

  it 'has a Knapsack (container of Goods) with a 4lb maximum' do
    expect{ Knapsack.new << 2 }.
      to raise_error('2 must be a Good to go in Knapsack')
    expect{ Knapsack.new << stereo << laptop }.
      to raise_error('Knapsack overcapacity!')
    expect(Knapsack.new << guitar << laptop).to be_a(Knapsack)
  end

  it 'will #steal_optimally_from(House)' do
    expect(thief.steal_optimally_from(house).knapsack).
      to match_array([guitar, laptop])
  end
  
  it 'definitely grabs your iPhone, too' do
    expect(thief.steal_optimally_from(house_with_iphone).knapsack).
      to match_array([iphone, laptop])
  end
end