Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #!/usr/bin/env ruby
- #
- # knapsack problem solution by backtracking.
- #
- # from:
- # Cプログラマのためのアルゴリズムとデータ構造
- # ISBN:4797304952
- # pp. 348
- #
- # author:
- # mootoh@gmail.com
- #
- require 'pp'
- $stuffs = [ # [size, value]
- [2, 2],
- [3, 4],
- [5, 7],
- [7, 11],
- [9, 14]]
- $values = {}
- def knapsack_bt(m, stuffs, sofar)
- stuffs.each do |stuff|
- if stuff.first > m
- sum = 0
- sofar.each {|s| sum += $stuffs.find {|x| x.first == s}.last}
- $values[sofar.map {|so| $stuffs.map {|s| s.first}.index(so) }] = sum
- next
- end
- knapsack_bt(m - stuff.first, stuffs, sofar+[stuff.first])
- end
- end
- def knapsack(m)
- stuffs = $stuffs.sort { |x, y| x.first <=> y.first }.reverse
- results = []
- knapsack_bt(m, stuffs, [])
- pp $values
- print 'result: '
- pp $values.sort {|x,y| x[1] <=> y[1]}.last
- end
Add Comment
Please, Sign In to add comment