Yesterday I've thought of a problem which is in short like the following:
Given a weighted graph, you have to create a forest, where each tree has weight (sum of the weights of edges) no more than K. You have to minimize the number of trees in that forest.
So, when I tried to think about its possible solution, at first MST popped in my head, but after hours of trying, I've found counter cases for all sorts of MST based greedy approaches. And finally, I think I am only able to solve this problem if n <= 20 or so...
Can anyone give me any idea if I can solve it for even larger number of nodes? I do not know cs theory much, does it belong to NP group?
Thanks in advance 
