beth,
Well, if the solution space weren't so incredibly large, I would suggest looking at a dynamic programming solution - but I have even less time to try that since it is an area I am still weak in.