はじめに

毎月先輩から出していただいた課題に取り組んでいます、 mi0です。
11月は 価値が大きくなる組み合わせ問題、いわゆる最適化問題を解きました。
この記事は解く〜レビューをいただくまでの過程を纏めた備忘録です。
こうやったらもっとよくなる、などのご指摘があればコメント頂けると嬉しいです！

過去の記事はこちら！↓

登場人物

私
- 社会人２年目PG。3年目が最近の恐怖ワード。最近異様に#selectを乱用している気がして不安になってきた。
出汁巻先輩
- オムレツちゃんの先輩。大根おろしはほどほどにしてほしいと思っている。コーディングが得意。
オムレツちゃん
- 私の心の中に住んでいる妖精。ケチャップはしっかりかけて欲しいらしい。

出題された問題

価値が大きくなる組み合わせ問題

問題

価格と重量のある、いくつかの品物を重量制限のある入れ物で運ぶ際、価格の合計が大きくなる組み合わせを出力する

メニューの元データ

db/data.csvから取得

要求仕様

詰め込む入れ物の重量制限は指定できる
品物は 1 つずつ詰め込むことができる
- 同じ商品を複数詰め込むことができない
提案する組み合わせ数は指定できる
- 組み合わせは価格が大きくなる順に並び替える
  - 価格が同じ場合は、重量の重い順に並び替える
- 組み合わせる品物はidの昇順
引数値の検証は不要
- 0 <= 入れ物の制限 <= 13
- 0 <= 提案する組み合わせ数 <= 10
使用するデータの価格と重量の組み合わせはユニーク
- 例) 価格: 2、重量: 3 の商品は 1 つのみで複数あることは考慮しないものとする
1 つも品物を詰め込まない組み合わせは除外すること
処理が複雑になる場合は、コメントや gem を追加しても良い

メソッドの返す値の形式

例）下記の形式（答えでは無い）
Array
- Hash
  - key: Symbol
  - value:
    - total_price: 合計価格
    - total_weight: 合計重量
    - records: Array
      - Hash: CSV の１レコード（一部型変換）
        
        key: Symbol
        
        value:
        
        id: Integer
        
        price: Integer
        
        weight: Integer

[
  { records: [{ id: 1, price: 1, weight: 1 },
              { id: 2, price: 2, weight: 2 },
              { id: 3, price: 3, weight: 3 }],
    total_price: 10,
    total_weight: 10 },
  { records: [{ id: 1, price: 1, weight: 1 },
              { id: 2, price: 2, weight: 2 }],
    total_price: 9,
    total_weight: 9 },
  { records: [{ id: 1, price: 1, weight: 1 }],
    total_price: 8,
    total_weight: 8 }
]

※CSVの中身は以下。

data.csv

id,price,weight
1,2,3
2,3,4
3,2,1
4,3,2
5,6,3

フェーズ１　自分で考える

私「CSVかぁ…………（バッチバチのRubyでCSVいじったこと無くないか？って顔）」

オムレツちゃん「大丈夫、それくらいならチョチョイよ！それにしても出汁巻先輩、なかなかの問題を出してきたわね……！」

私「そーなの？何となく出来そうな気がしているんだけども……組み合わせを作っていくんでしょ？その組み合わせを作るのも、パターンだからメソッド使ったらうまいこと出来るんじゃないかなあ（無知）」

オムレツちゃん「（大丈夫かしらこいつ……）」

私「とりあえず全然イメージ湧かないから具体的に組み合わせを作ってみよう！」

私「とりあえず価値が大きいものからぶち込んでいけばその入れ物の中の価値は最大になるんじゃないかな？同じ価値の場合は重量が軽いものを優先的に入れる。と、いい感じに組み合わせが作れるんじゃないでしょうか！」

私「実際のデータを使って纏めてみよう！」

私「ふんふん、具体的な組み合わせがあると考えやすいな〜。これでテストデータも出来たようなものだし、ガシガシ書いて行こう」

私「やることとしてはこんな感じかな〜」

ソートされたデータを作る
袋の容量よりも大きいものは除いておく
大きいものから入れられるだけ袋に詰める
詰めたものの中で可能な組み合わせを作る
組み合わせを元に重量と価値を計算する

実際に解いていく

私「よし！かくぞ！」

私「出汁巻先輩から事前にいただいたコードは……と。」

require 'csv'

class Suggest
  def initialize(limit, combinations)
    @limit = limit
    @combinations = combinations
    @data = CSV.read('db/data.csv', headers: true)
  end

  def result
    []
  end
end

私「なるほどなるほど……CSVの取り込みのところだけ少しいじろうかな。ヘッダーの情報とかいらないもんな」

require 'csv'

class Suggest
  def initialize(limit, combinations)
    @limit = limit
    @combinations = combinations
    @data = CSV.read('db/data.csv', headers: true)
  end

  def result
    sorted_data.map { |data| create_suggest(data) }[0..(@combinations - 1)]
  end
end

私「ついでにresultメソッドの理想形も書いておいたぞ！ソートしたデータを使ってなんかメソッド呼んだらいい感じの配列ができて、そこから指定範囲分取り出す！いい感じじゃない！？」

私「もう少し具体的にcreate_suggestを書いておこう………」

require 'csv'

class Suggest
  def initialize(limit, combinations)
    @limit = limit
    @combinations = combinations
    @data = CSV.read('db/data.csv', headers: true)
  end

  def result
    sorted_data.map { |data| create_suggest(data) }[0..(@combinations - 1)]
  end

  private

  def create_suggest
    create_records.map do |result|
      {
        result: result,
        total_price: result.sum { |item| item['price'].to_i }
        total_weight: result.sum { |item| item['weight'].to_i }
      }
  end
end

私「組み合わせを作ってくれるcreate_resultメソッドを呼んだ後に欲しい形にデータを整形してくれるメソッド！うんうん、大まかn

私「よしよし……次はデータをソートしよう！」

require 'csv'

class Suggest
  def initialize(limit, combinations)
    @limit = limit
    @combinations = combinations
    @data = CSV.read('db/data.csv', headers: true)
  end

# 中略

  private

  # 中略

  def sorted_data
    @data.sort_by { |data| data['price'].to_i }.reverse.map do |data|
      { id: data['id'].to_i, price: data['price'].to_i, weight: data['weight'].to_i }
    end
  end
end

私「まずsort_byで価値順に並び替える。sort_byだと価値が低い順に並んじゃうからreverseメソッドで価値が高い順に並び替える。その上でそれぞれの値を文字列から数値に置換しておくよ。以降の処理では値のことを気にしなくてよくなるもんね！」

※sort_byのブロック内のdata['price'].to_iを負の数にしてあげるとreverseが不要になることに後日気付きましたが、直感的じゃないような気も……。メソッド呼び出しが少なくなるから-(data['price'].to_i )みたいに書いてあげるのがいいんでしょうか……

私「次はそれぞれの組み合わせを作ってくれるメソッドを作ろう！」

require 'csv'

class Suggest
  def initialize(limit, combinations)
    @limit = limit
    @combinations = combinations
    @data = CSV.read('db/data.csv', headers: true)
  end

# 中略

  private

  def sorted_data
    @data.sort_by { |data| data['price'].to_i }.reverse.map do |data|
      { id: data['id'].to_i, price: data['price'].to_i, weight: data['weight'].to_i }
    end
  end

  def create_records
    sorted_data.each_with_object([]) do |record, array|
      next if @limit < record[:weight]
    end
  end
end

私「とりあえずソートしたデータを使って配列を作るからeach_with_objectを使うよ〜！そんでもって袋の重量を超過している品物は最初から省いてしまう処理を書いておく。」

私「次は袋に入るだけ詰め込んでいくよ〜！」

私「サンタクロースみたいで楽しいね！（？？？？？？）」

require 'csv'

class Suggest
  def initialize(limit, combinations)
    @limit = limit
    @combinations = combinations
    @data = CSV.read('db/data.csv', headers: true)
  end

# 中略

  private

  def sorted_data
    @data.sort_by { |data| data['price'].to_i }.reverse.map do |data|
      { id: data['id'].to_i, price: data['price'].to_i, weight: data['weight'].to_i }
    end
  end

  def create_records
    sorted_data.each_with_object([]) do |record, array|
      next if @limit < record[:weight]

      array << create_records_pattarn_array
    end
  end

  def create_records_pattarn_array
    sorted_data.each_with_object([]) do |target_item, result|
      result << target_item if result.sum { |r| r[:weight] } + target_item[:weight] <= @limit
    end
  end
end

私「今ある品物の中で一番価値の高い組み合わせを作る。それを最終的な組み合わせを格納するarrayに入れるよ。」

私「で、この最大の組み合わせから作ることのできる全パターンを作ればいいんだけど……。」

私「ど………………………………………………………………。」

私「これ組み合わせの個数バラバラじゃんね……………………？」

私「combination使えないじゃんね……………………？」

オム「気付くのおそ………………」

require 'csv'

class Suggest

  # 中略

  private

  # 中略

  def create_records
    sorted_data.each_with_object([]) do |record, array|
      next if @limit < record[:weight]

      pattarns = create_records_pattarn_array
      array << pattarns
      [pattarns.first].product(pattarns - [pattarns.first]).each { |p| array << p } if pattarns.size > 2
    end
  end

  # 略

end

私「３つ入っている時は、６つの組み合わせが作れるように、3つ以上品物が入っている時はそれぞれの組み合わせを作れるはず。」

私「１回のループでその組み合わせは作りきれないから、ひとまず今できている組み合わせの、一番最初に入っているものベースで作れる組み合わせを全部作る。」

私「create_recordsを全部回し切ったら全パターン作れてるはず！」

オム「それだと被りが出ちゃうんじゃない？」

私「う、うーん……」

私「uniqで……。」

オム「ダメじゃん……………。」

私「これだと処理がめちゃ遅なのは分かるんだけど……今の私ではもう……これくらいしか思い浮かばない……。」

〜〜その後、create_recordsをベースにデータを整え返すような実装に整えた結果が以下〜〜

require 'csv'

class Suggest
  def initialize(limit, combinations)
    @limit = limit
    @combinations = combinations
    @data = CSV.read('db/data.csv', headers: true)
  end

  def result
    create_suggests.sort_by { |suggest| suggest.values_at(:total_price, :total_weight) }.reverse[0..(@combinations - 1)]
  end

  private

  def sorted_data
    @data.sort_by { |data| data['price'].to_i }.reverse.map do |data|
      { id: data['id'].to_i, price: data['price'].to_i, weight: data['weight'].to_i }
    end
  end

  def create_suggests
    records_array = create_records
    return [{ records: [], total_price: 0, total_weight: 0 }] if records_array.empty?

    records_array.map do |records|
      {
        records: records.sort_by { |record| record[:id] },
        total_price: records.sum { |record| record[:price] },
        total_weight: records.sum { |record| record[:weight] }
      }
    end.uniq
  end

  def create_records
    sorted_data.each_with_object([]) do |record, array|
      next if @limit < record[:weight]

      pattarns = create_records_pattarn_array
      array << pattarns
      [pattarns.first].product(pattarns - [pattarns.first]).each { |p| array << p } if pattarns.size > 2
    end
  end

  def create_records_pattarn_array
    sorted_data.each_with_object([]) do |target_item, result|
      result << target_item if result.sum { |r| r[:weight] } + target_item[:weight] <= @limit
    end
  end
end

フェーズ２　レビューをいただく

　
出汁巻「じゃあレビューしていこう」

私「お願いします！」

出汁巻「まず私さんのコードなんだけど」

私「はい」

出汁巻「combinationsに0を渡すと組み合わせが全パターン取得できちゃうんだよね」

私「そんな…………」

出汁巻「これをよく見て」

reverse[0..(@combinations - 1)]

私「…………」

私「アッ！！！！！！！！！」

私「うそ……無理…ダメすぎる……これはダメ……[0..(0-1)]は[0..-1]で全部じゃん……ちょっとこれは恥ずかしすぎました……[0...@combinations]ですね…………」

出汁巻「そうだね。[0, @combinations]とも書ける。」

私「はい………」

出汁巻「次！#sorted_dataの中でデータをto_iしてたけど、せっかくなら#initializeの中でやった方がより良かったかな。sorted_dataの時点で同じキーの値にto_iを二回当ててたけど、そういうのがなくなる。」

私「あ……確かに。」

出汁巻「それから、以下みたいなコードは早期nextした方が可読性が上がるよ」

[pattarns.first].product(pattarns - [pattarns.first]).each { |p| array << p } if pattarns.size > 2

↓

next if pattarns.size <= 2

[pattarns.first].product(pattarns - [pattarns.first]).each { |p| array << p }

出汁巻「最後になんだけど……私ちゃんの処理、sorted_dataの個数分同じパターンを作ってたよ」

私「えっ」

出汁巻「以下のメソッド見て。」

def create_records
  sorted_data.each_with_object([]) do |record, array|
    next if @limit < record[:weight]

    pattarns = create_records_pattarn_array
    array << pattarns
    [pattarns.first].product(pattarns - [pattarns.first]).each { |p| array << p } if pattarns.size > 2
  end
end

def create_records_pattarn_array
  sorted_data.each_with_object([]) do |target_item, result|
    result << target_item if result.sum { |r| r[:weight] } + target_item[:weight] <= @limit
  end
end

出汁巻「sorted_data起点でやってるから、何回繰り返しても処理が走っちゃって、同じ組み合わせが出来ちゃうよね。これ、本当ならcreate_records_pattarn_arrayにrecordを渡すんだったんじゃない？」

私「…………………………………………（死）」

出汁巻「それから、重複する組み合わせが発生してるってことはその分余計なループが回ってるってことだから、その分処理も遅くなるよね」

私「はひ…………。」

出汁巻「この記事とかを参考にしたら、基本の考え方は分かり易かったと思う。私ちゃんは力技でやって一番いいパターンは正解するんだからすげーよ。」

私「あは……（頑張って具体例を出して考えたことが唯一活かされた瞬間）」

※以下、先輩の解答例コード

require 'csv'

#
# 組み合わせを提案するクラス
#
class Suggest
  #
  # 提案クラスインスタンス作成
  #
  # @param [Integer] limit 重量の上限
  # @param [Integer] combinations 組み合わせの要求提案数
  #
  # @return [Object] インスタンス
  #
  def initialize(limit, combinations)
    @limit = limit
    @combinations = combinations
    @data = CSV.read('db/data.csv', headers: true).map do |row|
      {
        id: row['id'].to_i,
        price: row['price'].to_i,
        weight: row['weight'].to_i
      }
    end
  end

  #
  # 結果を取得
  #
  # @return [Array<Hash>] 価値、重量の高い順の組み合わせ
  # @example
  #   Example return output:
  #
  #     [{:records=>
  #        [{:id=>2, :price=>3, :weight=>4},
  #         {:id=>3, :price=>2, :weight=>1},
  #         {:id=>4, :price=>3, :weight=>2},
  #         {:id=>5, :price=>6, :weight=>3}],
  #       :total_price=>14,
  #       :total_weight=>10},
  #      {:records=>
  #        [{:id=>1, :price=>2, :weight=>3},
  #         {:id=>3, :price=>2, :weight=>1},
  #         {:id=>4, :price=>3, :weight=>2},
  #         {:id=>5, :price=>6, :weight=>3}],
  #       :total_price=>13,
  #       :total_weight=>9},
  #      {:records=>
  #        [{:id=>1, :price=>2, :weight=>3},
  #         {:id=>4, :price=>3, :weight=>2},
  #         {:id=>5, :price=>6, :weight=>3}],
  #       :total_price=>11,
  #       :total_weight=>8}]
  #
  def result
    r = calculation.sort do |a, b|
      (b[:total_price] <=> a[:total_price]).nonzero? || b[:total_weight] <=> a[:total_weight]
    end

    r[0, @combinations]
  end

  #
  # 組み合わせの算出
  #
  # @return [Array<Hash>] 価値、重量、データ毎にまとめた組み合わせ
  # @example
  #   Example return output:
  #
  #     [{:total_price=>2,
  #       :total_weight=>1,
  #       :records=>[{:id=>3, :price=>2, :weight=>1}]},
  #      {:total_price=>3,
  #       :total_weight=>2,
  #       :records=>[{:id=>4, :price=>3, :weight=>2}]},
  #      {:total_price=>6,
  #       :total_weight=>3,
  #       :records=>[{:id=>5, :price=>6, :weight=>3}]}]
  #
  def calculation
    aggregate.inject([]) do |array, data|
      next array if data[:records].size.zero?

      array << {
        total_price: data[:value],
        total_weight: data[:records].map { |record| record[:weight] }.sum,
        records: data[:records].sort_by { |record| record[:id] }
      }
    end
  end

  #
  # 価値毎に集計した組み合わせ
  #
  # @return [Array<Hash>] 価値、重量、データ毎にまとめた組み合わせ
  # @example
  #   Example return output:
  #
  #     [{:value=>0, :records=>[]},
  #      {:value=>2, :records=>[{:id=>3, :price=>2, :weight=>1}]},
  #      {:value=>3, :records=>[{:id=>4, :price=>3, :weight=>2}]},
  #      {:value=>6, :records=>[{:id=>5, :price=>6, :weight=>3}]}]
  #
  def aggregate
    array = work_array

    @data.each do |data|
      (0..@limit).to_a.reverse.each do |i|
        next if array[i][:value].nil? || (i + data[:weight]) > @limit

        array[i + data[:weight]] = format_value(array[i], data)
      end
    end

    array
  end

  #
  # 集計時に使用する作業領域
  #
  # @return [Array<Hash>] 初期化された作業領域（重量の上限数 + 1）
  # @example
  #   Example return output:
  #
  #     [{:value=>0, :records=>[]},
  #      {:value=>nil, :records=>[]},
  #      {:value=>nil, :records=>[]}]
  #
  def work_array
    array = Array.new(@limit + 1) { { value: nil, records: [] } }
    array[0][:value] = 0
    array
  end

  #
  # 集計時に
  #
  # @param [Hash] value 加算先のHashオブジェクト
  # @example
  #   Example value output:
  #
  #     {:value=>0, :records=>[]}
  # @param [Hash] data 加算元のHashオブジェクト
  # @example
  #   Example data output:
  #
  #     {:id=>1, :price=>2, :weight=>3}
  #
  # @return [Hash] 初期化された作業領域（重量の上限数 + 1）
  # @example
  #   Example return output:
  #
  #     {:value=>2, :records=>[{:id=>1, :price=>2, :weight=>3}]}
  #
  def format_value(value, data)
    {
      value: value[:value] + data[:price],
      records: value[:records] + [data]
    }
  end
end

最後に

今回は初歩的なミスが目立ったのが良くなかったです。自力でやったが故に、迷走に迷走を重ねてしまったのも良くなかったです。もう少し既に存在する知識を調べて活用しなければ……と痛感しました。最適化問題、難しいですね……。考え方を理解した上で、有事の時に活かせるようにしたいです。