材料から必要な長さの素材を切り出すときの最適解

# 材料の長さ(今回は6000mm)
L = 6000

# 必要な長さと本数
# ここでは、1322mmを2本、1264mmを6本、1283mmを6本
needs = {
    a: {length: 1322, num: 2},
    b: {length: 1264, num: 6},
    c: {length: 1283, num: 6}
}

def culc(require_list)
  sums = []
  require_list.each do |k, v|
    v[:num].times do |i|
      # 配列をコピーして、キーを追加
      added_sums = Marshal.load(Marshal.dump(sums))
      added_sums.map{|el| el << k }
      
      # もとの配列とキーを追加した配列を結合
      sums.concat added_sums
      
      # キー単体を追加
      sums << [k]
      
      # 定尺を超えた物を削除
      sums.delete_if{|x| x.inject(0) {|sum, n| sum + require_list[n][:length]} > L}
      
      # 重複を削除
      sums.uniq!
    end
  end
  
  hashes = []
  sums.each do |nl|
    hashes << {pattern: nl, score: nl.inject(0) {|sum,n| sum + require_list[n][:length]}}
  end
  
  max_pattern = hashes.max{|a,b| a[:score] <=> b[:score]}
  
  p max_pattern
  
  max_pattern[:pattern].each do |item|
    require_list[item][:num] -= 1
  end
  
  require_list.delete_if{|k, v| v[:num] <= 0}
  
  if require_list.size > 0
    culc require_list
  end
end

puts "required list"
puts "====================================="
p needs
puts ""
puts "best combination"
puts "====================================="

culc needs