Class: Knapsacker

Inherits:
Object
  • Object
show all
Defined in:
lib/knapsacker.rb,
lib/knapsacker/node.rb,
lib/knapsacker/version.rb

Defined Under Namespace

Classes: Node

Constant Summary collapse

VERSION = 
"0.1.0"

Instance Method Summary collapse

Constructor Details

#initialize(items, capacity:) ⇒ Knapsacker

Returns a new instance of Knapsacker.



7
8
9
10
11
 
# File 'lib/knapsacker.rb', line 7

def initialize(items, capacity:)
  @items = items.sort {|a, b| b.value.to_f / b.cost <=> a.value.to_f / a.cost } # TODO assert cost
  @capacity = capacity
  @candidates = SortedSet.new
end

Instance Method Details

#grow(node, next_index) ⇒ Object 



26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
 
# File 'lib/knapsacker.rb', line 26

def grow(node, next_index)
  next_item = @items[next_index]

  if node.positive_child_growable?
    if next_item && node.cost + next_item.cost <= @capacity
      upper_bound = node.value + next_item.value + upper_bound_beyond(next_index, capacity: @capacity - node.cost - next_item.cost)
      node.positive_child = Node.new(next_index, next_item, upper_bound, node)
      @candidates << node.positive_child
    else
      node.cap_positive_child!
    end
  elsif node.negative_child_growable?
    if next_item
      upper_bound = node.value + upper_bound_beyond(next_index, capacity: @capacity - node.cost)
      node.negative_child = Node.new(next_index, nil, upper_bound, node)
      @candidates << node.negative_child
      @candidates.delete(node)
    else
      node.cap_negative_child!
    end
  end
end

#pack ⇒ Object 



13
14
15
16
17
18
19
20
21
22
23
24
 
# File 'lib/knapsacker.rb', line 13

def pack
  make_initial_node

  loop do
    node = select_node_to_grow
    if node
      grow(node, node.item_index + 1)
    else
      return node_with_highest_value.items
    end
  end
end

#upper_bound_beyond(prev_index, capacity: capacity) ⇒ Object 



49
50
51
52
53
54
55
56
57
58
59
60
 
# File 'lib/knapsacker.rb', line 49

def upper_bound_beyond(prev_index, capacity: capacity)
  index = prev_index + 1
  item = @items[index]

  return 0 unless item

  if item.cost > capacity
    item.value.to_f * capacity / item.cost
  else
    item.value + upper_bound_beyond(index, capacity: capacity - item.cost)
  end
end