変更された深さの最初の検索は総額を見つける

Question

免責事項：これは、仕事関連のクラスプロジェクトではありません。私は例をオンラインで見つけようとしましたが、一般的にはツリーを横断するためだけです。私はいくつかの他の条件で与えられた数に等しいであろう最大の可能な数の和の組み合わせを計算するためにDFSを使用しようとしていますC＃で

こんにちはすべて、

それをコーディングしています。

1. クラスの総重量の合計が150未満である必要があります。同じ身長と体重は、小さいIDを持つ人が最初に考慮される場合は、クラス内
2. 全高は、クラスA
3. に学生可能であれば、以上の600
4. 最大数にすることはできません。 150
   6から

ID - 重量 - 高
1から80 - 150
2 - 30から100
3から30 - 150
4 - 50から100
5から60 - 40から100

クラス1：1、2、6

クラス2：3、4、5

クラス3：

誰でも正しい方向に私を指すことができますか、この場合はDFSを使用しないでください。

Answer 1

DFSとBFSは、現在所有していないツリーで動作します。 IMOでは、可能なすべての組み合わせを持つツリーを作成することは、この場合正しい方法ではありません（ただし、もちろん実行できます）。あなたのセットが小さい場合は、ツリーを作成せずにDFSまたはBFSを使用せずに（@ Dennis.Verweijが提案しているように）すべてのソリューションを列挙することができます。

私はあなたの問題はそれ以外の場合はInteger Programmingを見てみましょう

残念ながら、NP完全であるKnapsack problemの変化、だと思います。これは解決するのは難しい問題ですが、ソリューションに役立ついくつかの関連アルゴリズム（実際には内部的にDFSを使用する可能性があります）を見つけることができます。