経緯
後輩から以下のようなLINEがきました。
「適切」という言葉が曖昧だが、以下のように解釈しました。
- 材料の本数が最小であること。
- 最後、余る棒の長さが最大であること。
要は、あまり材料を使わず、しかも、あまりを使いまわせるように出来る限り、長く取ろうという話。
とりあえず、俺なりの回答
Rubyで総当りのプログラムを作りました。ちょっと無駄は多いけど、まぁ、ひとまず動くのでいいかなと思います。
L = 6000 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
出力はこんなかんじ。
考察
この問題は部分和問題の類似問題かなーと思いました。
部分和問題とは、たとえば
[1,4,5,9]を適当に組み合わせて和が12になるようにできるか?
というような問題。この場合は、回答はNoです。どれだけ頑張っても12は作れません。
今回の問題はピッタリになることは通常ないと思うので、12以下の最大の値を作るためにはどうすればいいか?という話です。
たぶん、動的計画法に類似した方法になっているのかなーと思います。
こんにちは。貴ブログ偶然見つけました。
>この問題は部分和問題の類似問題かなーと思いました。
カッティングストック問題(cutting stock)と呼ばれています。
生産現場等、身近に多くの事例があり、見かけは易しそうだが
実は一般的な問題の最適解を得るのは非常に難しい問題です。
提示されたサンプルは小規模なので容易に最適解が得られますが。
計算機科学の分野でNP-Hardの難問です。
最適解を追及するのは大学の研究レベルですね。
因みに上記の数値例をExcel VBAのプログラムで求めた解は、
2本×[1283, 1283, 1264, 1264]
2本×[1322, 1283, 1264]
となり、カッティングパターンは2種類でも可能です。ご参考まで。
コメント有難うございます。
カッティングストック問題っていう名前なんですねー。
上のLINEのやりとりでも、実は言うと、この後、「NP困難じゃねーかふざけんな。」と答えていますw ただ、自分は優しい先輩なので、それなりのものを作ってみました。
大規模なら最適化をもっとしっかり考えないといけませんが、それなりに無駄なければいいかー、くらいなら、今回ので十分なのかなーと思います。