経費精算で損しないために

posts/2019-11-30diary

この記事はGMOペパボ Advent Calendar 2019の5日目の記事です。

GMOペパボ株式会社に入社して半年が経ちました。
今年2月に開設された鹿児島オフィスに勤務しています。

GMOペパボ鹿児島オフィスって？

GMOペパボが鹿児島にエンジニア部門の地方拠点「GMOペパボ鹿児島オフィス」を開設　〜テクノロジーをキーワードに人や企業をつなぐハブとなり地域と共に発展する企業を目指す〜

今回は経費精算で損しない方法について書きます。

経費精算って？

ペパボにはランチに関する福利厚生があります。

しかし開設されたばかりの鹿児島オフィスにはこれらの制度がまだないのです。
そのため鹿児島オフィスのパートナー(社員)は月に5000円まではランチなどの領収書を切っていいことになっています。むしろ一番自由度が高くて最高ですね！

毎日ランチに行ったとして20枚くらいの領収書があります。その中からいくつか選んで5000円以内に収まるようにして経費精算します。
おわかりのようにテキトーに選んじゃうと最適な組み合わせにならずに損してしまいます。

例えばこんな感じで領収書が12枚あったら。

230円, 330円, 450円, 500円, 510円, 520円, 530円, 600円, 700円, 1000円, 1640円, 1890円

この中から5000円に一番近い組み合わせをパッと選ぶのは無理ゲーです。
試しにこんな感じで選んでみると、、、

230円, 510円, 520円, 530円, 600円, 700円, 1890円 => 合計 4980円

おっ結構いい感じっぽい・・・でも今回の領収書のセットだとぴったり5000円になる組み合わせが存在します。20円も損してるのです。

そんなわけで、プログラムで領収書の最適な組み合わせを求めます。1円たりとも損しないように。塵も積もれば寿司になると信じて。

規定内に収まる最適な領収書の組み合わせを求める

Rubyだとこんな感じです。receiptsが領収書（金額）を表しています。

receipts = [230, 330, 450, 500, 510, 520, 530, 600, 700, 1000, 1640, 1890]

limit = 5000
max = 0
max_comb = []

[0, 1].repeated_permutation(receipts.size) do |bits|
    comb = bits.map.with_index {|v, i| v * receipts[i]}
    sum = comb.sum
    next if limit < sum || sum < max
    max = sum
    max_comb = comb
end

puts "#{max_comb} (#{max}YEN)"

これを実行すると、全組み合わせの中で一番5000円に近い最適なものが出力されます！！

[230, 330, 450, 500, 0, 0, 0, 600, 0, 1000, 0, 1890] (5000YEN)

だいぶ見辛いですが、0以外の金額になっている領収書の組み合わせでちょうど合計5000円になるってことです。

コード的には、よーしパパ全探索しちゃうぞーって感じです。

単純に考えて全ての組み合わせを試せば一番いい組み合わせがわかります。
各領収書について「選ぶ」「選ばない」の2択なので、領収書が$$N$$枚あったら組み合わせの数は$$2 ^ N$$。
領収書はたかだか20枚なので$$2 ^ {20} = 1,048,576$$通りくらいです。これくらいなら十分高速に試せそうな気がするし、実際試せます。

全ての組み合わせを試す方法として、bit全探索と呼ばれる手法を使っています。
bit全探索というのはざっくりいうと、ある集合の部分集合を全て列挙するのに便利な手法のことです。各桁のビットを使って部分集合を表します。

例えば{A, B, C}という集合があって、これらの部分集合が欲しいな〜って気持ちになったとします。
（つまり各要素について選ぶ/選ばないを行った結果が欲しい）

0のビットを「選ばない」とみなし、1のビットを「選ぶ」とみなせば、全ての組み合わせはこんな感じで表せます。

000 -> {_, _, _}
001 -> {_, _, C}
010 -> {_, B, _}
011 -> {_, B, C}
100 -> {A, _, _}
101 -> {A, _, C}
110 -> {A, B, _}
111 -> {A, B, C}

000〜111は0〜7の2進数表記になってますね！
このビットの集合を作るために、RubyのArray#repeated_permutationを使っています。

irb(main):001:0> [0, 1].repeated_permutation(3).to_a
=> [[0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 1, 1], [1, 0, 0], [1, 0, 1], [1, 1, 0], [1, 1, 1]]

便利！！！１
しかも0, 1の配列なので、これをそのまま総和の計算に使えます！

こういう便利メソッドがない言語だと、

for bit := 0; bit < (1 << len); bit++ {
    for i := 0; i < len; i++ {
        if 1 & (bit >> i) == 1 {
            bitが立ってるとき
        } else {
            bitが立ってないとき
        }
    }
}

みたいに書けますが、正直なんだこれーってなりますね。

bit全探索は部分集合を列挙したいときに便利な手法で、Rubyだとめちゃくちゃ簡単に書けて最高って話でした。

実際に経費精算するときはこんな感じでSlackBotに投げています。botが最適な組み合わせの結果を返してくれます。

領収書が増えるとダメ

お気付きの通り、この「全ての組み合わせを試す」方法だと領収書の数が増えると計算量がやばいです。現実的な時間では終わらなくなります。$$O(2^N)$$ですから……。

この計算量を改善する発展編は来年のペパボアドベントカレンダーで書きます！！１（たぶん）

まとめ

こうして選んだ領収書を経費精算しています。
でも手で領収書の配列を作るのはなんともいけてない感じがします。SlackBotでやってるのも含めてその辺りをもっといい感じにしたいですね。来年のアドベントカレンダーではそのあたりを改善したよって記事が何者かによって書かれるかも知れません。

まあ制度自体が変わってるかもしれないですけど。

追記

このエントリを読んだ同僚のpurple_jwlさんが、計算量を改善するエントリを書いてくれた！！１

「経費精算で損しないために」の続き - ぱーぽーの日々

DPで最適解を求めて、使った領収書を復元するというもの。
領収書の枚数を$$N$$、月の上限額を$$M$$とすると、計算量は$$O(NM)$$になる。

お手本のような解法でめちゃくちゃ勉強になる。