ゲームTiny Towerには、さまざまな属性でスキル 0 ～ 9 のさまざまな「Bitizens」があります。
Michael:
a) retail: 9
b) creative: 2
c) service: 7
d) recreational: 4
e) food: 6
そして、3人のビティズンが働けるビジネスがあります。各ビジネスは、小売、クリエイティブ、サービス、レクリエーション、食品のいずれかのカテゴリに分類されます。ビジネスまたは Bitizen の数が一致することは決してありませんが、簡単にするために、ポジションの数が Bitizen の数と一致すると仮定できます。
たとえば、小売業である帽子屋があり、価値の高いビチズンretailが好まれます。上記の例では、Micheal は小売業に非常に適しています。
アルゴリズム的に、最も適切なスキルを持つ Bitizen をポジションに配置するにはどうすればよいですか? 私はその問題に挑戦しようとしましたが、実際に問題を効果的に解決する方法で頭を悩ませました。
余分な「ポイント」は、どこに置いても同じように価値があると仮定しましょう。たとえば、クリエイティブとフードの2つのビジネスがある場合、それぞれ11個持つよりも、クリエイティブで20個、フードで3個の合計の方が常に良いと想定します。
その場合、あなたの問題は割り当て問題の例です。これは、多項式時間、特に時間O（n ^ 3）で解くことができるという点で「簡単」であることが知られています。ハンガリーのアルゴリズムは、この問題を解決するための標準的な方法です。非常に詳細なウィキペディアのページよりもうまく説明することはできませんが、そこで何かに行き詰まっている場合は、質問してください。
膨大な数のビチズンや企業がいて、このアルゴリズムが実行不可能な場合、シミュレーテッドアニーリングや進化的アルゴリズムなどの近似的な方法で問題を攻撃するのは非常に簡単だと思います。
私の当初の仮定が正しくない場合（たとえば、各タイプの人員が豊富なビジネスを少なくとも1つ持つ方がよい場合）、ほぼ確実にこれらの不正確な方法を試す必要があります。特定の労働者とビジネスの割り当て順列の値を反映する目的関数の設計に集中します。
最小化する目的が 1 つだけになるようにすべての属性をまとめることができれば、割り当て問題で問題を解決できます。それ以外の場合、問題は NP 困難 なmulti-index assignment problem のようなものです。
したがって、合理的な解決策を見つけるために、特定のケースについて詳しく説明してください。