Ruby 価値が大きくなる組み合わせ問題 解いてみた

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

過去の記事はこちら！↓

- [「Ruby初心者向けのプログラミング問題を集めてみた」の電話帳問題解いてみた。](https://qiita.com/mi0/items/738b78fe5e7d10df34ae)
- [Ruby ボウリング問題解いてみた。](https://qiita.com/mi0/items/a8d4b90696ae4404e742)

### 登場人物
- 私
    - 社会人２年目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

```ruby
[
  { 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の中身は以下。

```csv:data.csv
id,price,weight
1,2,3
2,3,4
3,2,1
4,3,2
5,6,3
```

## フェーズ１　自分で考える
私「CSVかぁ…………（バッチバチの`Ruby`でCSVいじったこと無くないか？って顔）」

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

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

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

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

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

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

![IMG_0165.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/273022/52b1c600-4500-35ee-fdd5-e839194762fb.jpeg)

![IMG_0166.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/273022/1a283ec0-3ebf-1e2f-3381-e78c57d1dfe0.jpeg)

![IMG_0167.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/273022/1e445f17-0e7d-1f0b-b768-027c52ce224c.jpeg)

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

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


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


## 実際に解いていく

私「よし！かくぞ！」

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

```ruby
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の取り込みのところだけ少しいじろうかな。ヘッダーの情報とかいらないもんな」


```ruby
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`を書いておこう………」

```ruby
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

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

```ruby
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 )`みたいに書いてあげるのがいいんでしょうか……:thinking:

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

```ruby
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`を使うよ〜！そんでもって`袋の重量を超過している品物は最初から省いてしまう`処理を書いておく。」

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

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

```ruby
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`使えないじゃんね……………………？」

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

```ruby
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`をベースにデータを整え返すような実装に整えた結果が以下〜〜

```ruby
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を渡すと組み合わせが全パターン取得できちゃうんだよね」

私「そんな…………」

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

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

私「…………」

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

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

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

私「はい………」

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

私「あ……確かに。」

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

```ruby
[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`の個数分同じパターンを作ってたよ」

私「えっ」

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

```ruby
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`を渡すんだったんじゃない？」

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

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

私「はひ…………。」

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

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

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

```ruby
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
```

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