アルゴリズムの問題

アルゴリズムの問題で困ったことがあり答え及びヒントをくれたら嬉しいです。「n個の自然数が与えられ、n個の自然数を2グループに分割したとき、各グループの和がともに奇数になるものがあるか」
下記にある画像を参考して答えろと言われました。

質問者からの補足コメント

• either-or文は都合のいい選択をする、非決定的に推測できる計算モデル命令みたいです。非決定的アルゴリズムには推測と確認のプロセスが必要で、最後には確認のやつがあります。

    補足日時：2019/06/21 12:16

No.4 ベストアンサー 回答者： ゼロプライム 回答日時： 2019/06/20 22:43

No.2の続きです。

ｎ個の自然数の和が偶数。
更に、ｎ個のうちに奇数が偶数個必要。
そして、２つのグループに分ける時に、その奇数を奇数個ずつ分ければ、どちらのグループの和も奇数になります。

No.6 回答者： ありものがたり 回答日時： 2019/06/21 04:06

奇数の個数だけの問題じゃないことは、

{ak}={10000,1,1}と{10000,1,1,1}を比べてみるだけでも判る。
どちらも Σ[i∈A]ak=Σ[i∉A]ak にゃなるまい。

No.5 回答者： Tacosan 回答日時： 2019/06/21 00:15

その画像の「『分割問題を解くアルゴリズム』を参考」にしてもいいけど, それでも #2 の視点は重要だねぇ. これがあれば O(n) で実現できる. もっとも参考にしなければはるかに簡単で, #4 から

奇数の個数を数える
だけ.

あと, 問題が「各グループの和がともに奇数になるものがあるか」なので「実際のグループ分け」まではしなくていいです＞#1.

No.3 回答者： ありものがたり 回答日時： 2019/06/20 22:31

各グループの和が奇数か偶数かの話というより、

{ak}が和の等しい２グループに分けられるか否かという問題でしょ？
そのためには、{ak}の総和が偶数であるだけでは十分でない。
和の等しい２グループに分けられるならば、その和が奇数か偶数かは
{ak}の総和を4で割った余りが2か0かですぐに判定できる。

和の等しい２グループに分けられるかどうかは、要するに詰め込み問題だから、
全数検査よりマシな解法はヒューリスティクスしかない。
なんとなく早めに解が見つかりそうな順番で、全数検査をやってみるしか。

その写真の「アルゴリズム」は、either ... or ... のところで
並列計算を行うことでも想定しているのだろうか？ 謎。
並列度 2^n が実現できるのでなければ「全体でO(n)ステップ」にはならないが。

No.2 回答者： ゼロプライム 回答日時： 2019/06/20 22:14

ｎ個の自然数の和が奇数の時は、どのように２つのグループに分けたとしても、一方のグループの和は奇数で、もう一方のグループの和は偶数です。

ｎ個の自然数の和が偶数の時は、どちらも奇数になるときはあります。
例えば、｛1,2,3｝を｛1,2｝と｛３｝に分けます。

No.1 回答者： varietyknowledge 回答日時： 2019/06/20 22:07

このアルゴリズムは各グループの和がともに奇数になるか判定するのではなく、各グループの和が等しいかどうか判定するものなので、参考にならないですね。

さらに書くと、どうやってグループ分けするかも不明です。

よく分からないプログラミング言語ですが、自分ならmod（剰余）を使って余りが1かどうかを判定する処理にしますかね。
（正直グループ分けのほうが面倒）