天才火消しエンジニア霧島「もしPMおじさんが丸投げを覚えたら」|paizaオンラインハッカソンLite
20140804追記:コードを少し高速化してみました
オブジェクティブ氏に改善を求めてみた - せでぃのブログ
他称チャッカマンの火村さんが納期残り1ヶ月で、案件を下請けに丸投げ、女子高生っぽい26才天才火消しエンジニアの霧島さんまでもが「ホームページ公募で」、第三者に丸投げしてきたので、Objective-Cで消火活動を応援してみた。
消火活動と言っても、たぶんマトイを振り回してるだけw
提出前チェックで弾かれて面倒くさくなったのでgithubに上げた。参加せず。いやいや、こっちだとエラーなしで動くから。
それより、こんな言語選択で大丈夫か? 特別なフレームワークがいらんのなら、Cシェルなりパワーシェルで十分なんじゃないの?
csny/enjou · GitHub
「ナップサック問題」という結構有名な問題らしい。ほぼコピペとか言ったらいけません。
組み合わせ数は、nCrで更にこのrが階乗になる。n!/(n-r)!r!のrが階乗なので、深く考えたり電卓叩いてみようとか思ったらあきません。変数はほとんどlong型になりました。
考え方は簡単で、条件を比較しながら再帰呼出で枝を広げて、50桁の2進数を総当たりする感じ。
0 | 1 | 2 | 3 | … | n | … | 49 |
---|---|---|---|---|---|---|---|
0 | 1 | 1 | 0 | … | - | … | 0 |
0 | 1 | 1 | 0 | … | - | … | 1 |
本当は「枝落とし」という、何らかの条件で探索を途中で切り上げたりするもんらしいけど、この課題だと人月の上限以外で枝を落とす理由が見当たらないんだよね。だからほぼ全探索することになった。
それだけでは面白くないので、会社数が多い場合は、人月が多そうなところから適当にソートする仕組みを入れてみた。たぶん、それほど効率変わらん。動くんだから何も言ってくれるなw
この納期って何? 見積もりの納期なの? システムは入れなくて大丈夫なの?
まぁ、火村さんの度胸だけは見上げたもんですわw 大手のPMたるもの、こうありたいwww
objcの環境がないけどコードが見たいという方はこちら。
https://github.com/csny/enjou/blob/master/enjou/main.m
単純な問題みたいだけど、コーディングは楽しい。