修改深度首先搜索找到總和

Question

免責聲明：這不是一個類項目，更多的工作相關。我嘗試在網上找到示例，但通常只是通過樹來遍歷。我編碼在C＃中

大家好，

我試圖使用DFS來計算可能的最大數量和結合，這將是等於與一些其他條件給定數。

1. 一個班級的總重量需要低於150。
2. 在類總高度不能學生如果可能超過600
3. 最大數目在甲
4. 類如果相同的高度和重量，具有較小ID的人將首先考慮。

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

第1類：1，2，6

類2：3，4，5

第3類：

任何人都可以指向正確的方向或DFS不應該在這種情況下使用？

Answer 1

DFS和BFS適用於您目前沒有的樹木。國際海事組織，創建一個包含所有可能的組合的樹在這種情況下不是正確的方式（但當然你可以做到）。如果你的設置很小，你可以嘗試枚舉所有的解決方案，而不用創建一棵樹並使用DFS或BFS（如@ Dennis.Verweij所提出的）。

我覺得你的問題是Knapsack problem的變化，這是不幸的是NP完全

否則看一看Integer Programming。這是一個難以解決的問題，但您可以找到一些相關算法（實際上可能使用內部DFS）來幫助您解決問題。