硬貨の問題が貪欲法で解けるための条件
硬貨の問題とは A円支払うために必要な硬貨の枚数を最小にする組み合わせを求める問題。 コインの問題、お釣り生成問題（Change-Making Problem : CMP）、とも呼ばれる。 この問題は競技プログラミング等で貪欲法を用いて解かれることが多いですが、貪欲法で最適解が求まることは自明ではありません。 貪欲法で解ける場合 例えば、日本の通貨体系（1円、5円、10円、...）では、価値の大きい硬貨から順に使っていく貪欲法で最適解を求めることができます。 貪欲法で解けない場合 仮に日本の通貨に新しく8円硬貨が追加されたとします。 16円を支払うとき、貪欲法で考えると、10円、5円、1円の3枚の硬貨で支払うことになります。 しかし、明らかにこれは最適ではなく、8円硬貨2枚で支払ったほうが硬貨が少なく済みます。 貪欲法で解ける条件は？ 硬貨の問題は整数ナップサック問題の特殊型であり、整数ナ
マイクロサービスが Scala を選ぶ３つの理由 - Okapies' Archive
今年も開催される Scala Advent Calendar 2014 の 15 日目にエントリーしていて、ネタとしては先日 Tumblr が発表した "I/O and Microservice library for Scala" を謳う Colossus をやる予定なんだけど、前振りとして「なぜマイクロサービス化を進めるサービスは Scala を選ぶのか」という話をしてみるエントリ。ちなみに、Advent Calendar の前振りと書いたけど、とりあえず Scala をあまり知らない人向け。 そもそもマイクロサービスって何だっけ？ マイクロサービスへの移行と Scala なぜ Scala が選ばれるのか？ 1. JVM 言語である 2. Finagle の存在 性能 プログラミングモデル 運用ツールとの連携 3. 静的型付き言語である 余談 そもそもマイクロサービスって何だっけ？ こ
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
https://kimiyuki.net/blog/2017/12/03/matroid-greedy-proof/
