2011-10-20 13 views
1

OK ...だから私はちょっと難しい(私のために、少なくとも)。有効な組み合わせの最大数を見つけるアルゴリズム?

私は単純なオブジェクトのリストを持っており、最大数を利用する組み合わせを見つける方法を理解する必要があります。これらのオブジェクトの各クラスは、名前のプロパティ(文字列)、結合する他の要素の名前のプロパティ(List)、他の要素の名前のプロパティ(List)を持っています債券に似ていない。

特定の要素が既にコレクション内にある他の要素の1つ(またはそれ以上)を「好き」しているコレクションに要素が追加された場合、追加された要素はコレクションの各項目に対して+1を返します好きです。同様に、追加された要素が好きではないコレクション内の他の各要素に対してスコア-1が返されます。すべての要素を最終コレクションに追加した後、それぞれのスコアは0以上でなければなりません。

最大のコレクションを返すために使用できる要素の組み合わせを見つけるにはどうすればよいですか?同じ数の要素を返す複数の組み合わせの場合、すべての可能な組み合わせを返す必要があります。

私はC#(.NET 4.0)を使用していますが、どのプログラミング言語も使用できるので、その背後にあるロジックを理解する必要があります。事前に

おかげで、
ソニー

+0

あなたが見ているオブジェクトの有限集合または特定の範囲のオブジェクトがありますか? 1つのオブジェクトをコレクション内で繰り返すことはできますか? – jball

+0

また、各アイテムにあらかじめ定義され固定されている「好き」と「嫌い」リストはありますか?それらはすべてのアイテムの長さが同じですか?長さが異なる場合は、アイテムを追加する前にアイテムを並べ替えることができます。 –

+0

関係は対称ですか?私は、AがBを好むならば、BがAを好んでいるということを意味し、AがBを嫌うならば、Bが嫌いであるということですか? –

答えて

2

私はあなたが、これは難しい問題であると言うことは正しいと思います。私はノード間のリンクに重みを与えるように、オブジェクトをグラフなどのノードとして考える/嫌いな情報を考えます。 "like"フィールドを無視し、すべてのリンクに重み0または重み-1を与えます。この場合、問題はノード間のすべてのリンクに重み0があり、いずれにも重み-1がないような最大数のノードを見つけることです。これを効率的に行うプログラムがあるとします。

ここでは、既知の問題である問題http://en.wikipedia.org/wiki/Clique_problemを見てください。最大クリークの問題がある場合は、すべてのノード間にリンクを作成します。 2つのノードが最大クリークでリンクされている場合は、重み0を設定します。リンクが存在しない場合は、重み-1を設定します。今あなたの問題を解決するプログラムを実行し、あなたは最大のクリークを解決しました。だから私はあなたの問題はNP-Completeだと思うし、効率的な解決策になることはまずありません。

+0

ありがとう、そのwiki atricleは私が説明しようとしていたものでした。私は最大で十二から十二のノードの間しか扱っていないので、私はそれを強制的に強制し、パフォーマンスがどのようになるかを見てみようと思う。 –

関連する問題