イベント物販最小購入個数問題

### 環境
* Office365 Excel Buisiness

### 背景
みなさんイベントでの特典目当てで物販購入する方多いと思います。もちろんお金の許す限り最大数購入したい。でも現実は甘くない、そういう状況です。そうなるとあのグッズは欲しいけど、このグッズは今回泣く泣く遠慮してとか悩んでいませんか？
そんな悩みを一瞬で理論で解決してしまおう。Excelにまかせてしまおうというのが今回の目的です。

### ナップザック問題
上記のような問題をナップザック問題というようです。以下、wikiより一部抜粋。

>ナップサック問題（ナップサックもんだい、Knapsack problem）は、計算複雑性理論における計算の難しさの議論の対象となる問題の一つで、「容量 C のナップサックが一つと、n 種類の品物（各々、価値 pi, 容積 ci）が与えられたとき、ナップサックの容量 C を超えない範囲でいくつかの品物をナップサックに詰め、ナップサックに入れた品物の価値の和を最大化するにはどの品物を選べばよいか」という整数計画問題である。

なんのこっちゃ。

### 今回の課題

次の表の用な物販情報が事前に出ました。￥5,000以上購入でチェキ撮影券がつくということです。
![SnapCrab_ソルバーxlsx - Excel_2019-8-30_10-4-39_No-00.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/160188/bed42f74-0a5a-463a-8226-62af2c69a60d.png)

普通に考えれば、上記組み合わせで￥5,000だと、生写真セット5セット。ちょっと考えればキーホルダー1つと巾着、生写真セット2セットという組み合わせが最安な組み合わせに思えます。たぶん事実です。ですが、最安だけではなく欲しいものがあったり数に制限があったらどうすればいいのでしょう。
また、もっと複雑な物販になったら時間をかけないとよい組み合わせが見つからないかもしれないです。

### 準備
ソルバーというアドインを使用します。僕の環境だと標準でアドオンにありました。
「オプション」-「アドイン」-「ソルバーアドイン」
![SnapCrab_Excel のオプション_2019-8-30_9-55-53_No-00.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/160188/652e698b-5611-0ff2-de9e-c32fd7d6457a.png)

下のほうにある設定を押してあげてソルバーアドインを有効にします
![SnapCrab_アドイン_2019-8-30_9-55-59_No-00.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/160188/ff63e6cf-1a2a-6ab3-7cec-257723e9764e.png)

データメニューの右端にソルバーが現れました
![SnapCrab_ソルバーxlsx - 保存しました_2019-8-30_9-58-7_No-00.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/160188/fb230355-6128-0b3a-c09a-c3a14c6a2b03.png)

### Excelでソルバーアドインを使う

#### 表を作成する

![SnapCrab_ソルバーxlsx - Excel_2019-8-30_10-11-13_No-00.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/160188/8d701319-fd09-4f70-65d9-454681650f8c.png)

上記のような感じです。

#### 条件を考えてみる
僕はアクリルスタンドキーホルダーは絶対ほしいです。この気持ちは
>\$C$3 >= 1

>\$C$4 >= 1

そう、1つ以上あってもいいです。好きだから。

お財布事情を考えると、なるべく￥5,000に近い金額の組み合わせを知りたい。チェキをとるためには合計で￥5,000以上購入しないといけないのだ。

>\$D$7 >= 5000

となる。

この気持ちをソルバーに投入する。
![SnapCrab_ソルバーのパラメーター_2019-8-30_10-25-49_No-00.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/160188/33d394d8-9581-2b1c-9bae-5e151a45b460.png)


[目的セルの設定]の項目に金額が表示される。上の表のようにSUM式で記載しておこう。普通のブランクのセルは指定できない。必ず数式のセルを指定する

* [目標値]は「なるべく安く」ということで最小値とする

* [変数セルの変更]は要は品物の購入個数ということになるから、物販の数の列を選択する

* [制約条件の対象]は僕の気持ちを入力する。整数条件を入れないと、Tシャツ0.25個とかになってしまうので入れないといけない。

※オプションとか見てもさっぱりわからない。数学とか分析の世界だ。ヲタクには関係ないということにする

あとは解決ボタンを押すと、C列の値が勝手に条件に合わせた最適な値になってくれる。
![SnapCrab_ソルバーxlsx - Excel_2019-8-30_10-31-10_No-00.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/160188/e2216827-d02d-4f20-7abb-9cf47da05f60.png)

今回はTシャツはあきらめるしかないということがわかる。

もっと推しとチェキが取りたくて、￥10,000払えるという強い人がいる場合の結果は以下である。とはいえ、希望する人全員がチェキ取れるようある程度配慮するのが信のツワモノである。
![SnapCrab_ソルバーxlsx - Excel_2019-8-30_10-33-49_No-00.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/160188/984dfac3-5a3f-cdc1-bb0e-1c04e388aa50.png)

生誕祭キーホルダーが3つになっているが、感謝祭と生誕祭それぞれ2個ずつでもよいだろう。

空気読まない強すぎる人でチェキを3枚撮りたい場合以下のような結果になった。このあたりはもう頭で考えるのはかなり時間がかかるのかもしれない。
![SnapCrab_ソルバーxlsx - Excel_2019-8-30_10-38-37_No-00.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/160188/d0471ff8-6162-f3ab-2628-e153c83f498e.png)

キーホルダーばっかりになってしまった。
強い人は、すべてのアイテム最低一つのような条件が必要かもしれない。


### 参考
[wikiナップザック問題](https://ja.wikipedia.org/wiki/%E3%83%8A%E3%83%83%E3%83%97%E3%82%B5%E3%83%83%E3%82%AF%E5%95%8F%E9%A1%8C)