0

Disclaimer: This is not a class project, more of work related. I tried finding example online but generally its just for transversing through the tree. I am coding it in C#

Hi all,

I am trying to use DFS to calculate the biggest possible number sum combination which will be equal to the number given with some other conditions.

  1. Total sum of weight needs to be below 150 in a class.
  2. Total height in the class cannot be more than 600.
  3. Max number of student if possible in Class A
  4. If same height and weight, the person with the smaller ID will be considered first.

ID - Weight - Height
1 - 80 - 150
2 - 30 - 100
3 - 30 - 150
4 - 50 - 100
5 - 60 - 150
6 - 40 - 100

Class 1: 1, 2, 6

Class 2: 3, 4, 5

Class 3:

Anyone can point me in the right direction or DFS shouldn't be used in this case?

user2866313
  • 23
  • 5
  • Hi, what am i missing? – user2866313 Aug 24 '17 at 10:34
  • Code, mainly... – mjwills Aug 24 '17 at 10:36
  • have you maybe considered to first get all subsets of the collection [as per this answer?](https://stackoverflow.com/a/999182/8135700) and then using linq statments to filter the results? this however will grow exponentially longer the more you put into the collection. – Dennis.Verweij Aug 24 '17 at 10:37
  • Will it be too expensive in terms of processing power to get all the subset? It should work fine within the range of 10 id but anything above 20, I believe the tree node is gonna be quite large. – user2866313 Aug 24 '17 at 10:49
  • You can make it asynchronous/multithreaded to speed it up. But it shouldn't clock out on you. – Dennis.Verweij Aug 24 '17 at 10:58

1 Answers1

1

DFS and BFS works with trees, which you currently do not have. IMO, creating a tree with all possible combinations is not the right way in this case (but of course you can do it). If your set is small you can try to enumerate all solutions without creating a tree and using DFS or BFS (as @Dennis.Verweij is proposing).

I think that your problem is a variation of the Knapsack problem, which is unfortunately NP-Complete

Otherwise take a look at Integer Programming. This is a hard problem to solve, but you can find some relevant algorithms (which might actually use internally DFS) to help you with the solution.

djvuk
  • 370
  • 3
  • 15