プログラム初心者の質問です アンドロイドアプリで最小化問題(的なモノ)は現実的？

androidアプリを作る課題が出ており自分は最小化問題的なものを解くアプリを作ってみたいと思っております。
もし作れそうであれば頑張ってみたいと思っているので結果が出るまでの時間を考えた場合　可能か不可能か (現実的に意味があるか/作ることができるか) だけでも知りたいと思っています。
いささか間抜けな質問だとは思いますが宜しくお願いします。


１００種類程度のものの中からそれら（a,b,c）の３つの項目の合計と目標値との差が最小になるように２つ選択する
利用する１００種類のデータは以下のようなデータになっています。
ID|name|a|b|c
01|aaa|10|5|12
02|bbb|9|4|14
・
・
目標値はそれよりも前に設定する予定です。

No.1 ベストアンサー 回答者： kmee 回答日時： 2016/09/25 18:32

課題、ということは、専門学校とか大学とかですか?

そうだとすると、授業で「計算量」って出てこなかったですか?

計算量を計算してみて、多項式オーダーなら可能、指数オーダーなら無理、というのが一つの目安です。


n個のデータから2つ選ぶ組合せは nC2 通り
最小値を探すために、上記から総当たりで比較するなら (nC2)C2 通り
合計して、O( t・ nC2+ s・(nC2)C2 ) の計算量となります。

最小値を探す方法が単純で1回の走査で済むなら nC2 で
合計して、O( t・nC2 + s・nC2 ) の計算量となります。

この回答へのお礼

学校ではなく　内輪で作ってみよう　というような勉強会のようなものでの課題です
そのため恥ずかしながらオーダーの知識は聞いたことある程度です。

オ−ダーについて調べてみようと思います。
ありがとうございます

お礼日時：2016/09/25 19:08

No.2 回答者： kmee 回答日時： 2016/09/25 22:11

そうでしたか。

計算量はちょっと複雑なことやらせようとすると避けられないものなので、頭の隅にでも留めておいてください。


オーダーを求めるのが難しいのなら、実際の値を求めてしまうのも手です。

例えば、総当たりで処理しようとしたら
for(i=0;i<n;i++){
for(j=0;j<n;j++){
処理
}
}
とかの2重ループにしますよね。
この「処理」が何回実行されるか、計算できるでしょう。

この回数に、1回あたり何秒、と適当に計算すれば、実行時間が見積もれます。

数を2倍とかして見積ってみれば、現実的かどうか予想できると思います

この回答へのお礼

ありがとうございます！
いろいろ計算してみた結果直書きでやるには非現実的でしたのでpythonでのソルバーや別のところで計算し結果だけ送流ようにしたいと思います。

まだ若干わかってないとは思いますが今後やりながら勉強していきたいと思います。

お礼日時：2016/09/26 18:55