Well, I really don't need help with code itself, but understanding what exactly I am trying to do in order to write the code. In a nutshell, I am given 1000 projects each with a set of resources, and I have a (set ammount) of resources to utilize to calculate what are the best projects I can pick.
the pseudocode for the bestprofit function is as follows:
Parameters -
projects: a vector of projects
r: the resources available to solve the subinstance
valueMap: the map data structure that is used for memoization
n: only projects numbered 0,...,n-1 may be
used to solve the subinstance
Returns - the maximum amount of profit that may be obtained on this
subinstance of the optimization problem
Post-condition – If n > 0, then valueMap contains an entry
whose key is (r, n).
If n equals 0
return 0
Check valueMap to see whether this subinstance has already been solved
- If so, then return the previously computed result (function terminates)
best1 = bestProfit(projects, r, valueMap, n-1)
Check whether r provides enough resources to undertake project n-1
- If so, then best2 = bestProfit(projects, r – projects[n-1].requirements, valueMap, n-1)
+ projects[n-1].profit
Else
best2 = 0
If best1 >= best2
Store (r, n) -> (best1, false) in valueMap
Return best1
Else
Store (r, n) -> (best2, true) in valueMap
Return best2
When I do the recursive call to bestProfit, best1 is supposed to check if a subproblem has already been resolved. and best2, considered the feasibility check is only based on the very last project. in other words it looks like a balanced tree. What I am unable to understand is how do I insert the values on the map during the recursion? Basically the final if/else statement won't happen until the whole set of projects has been traversed. And only the final value gets inserted on my map. I just want some pointers on how should I approach this to write the recursion correctly.
Like I said before I am not looking for code but a way to understand the requirements of this pseudo code for my project in C++. it is this logic that is driving me crazy at this point because I can't put it together to work. Thank you all for looking at this and providing a better insight if possible.
I'd return a data structure that indicates both the profit and the solution that gets that profit. Store that exact data structure in valueMap. This will make your code more straightforward.
Basically, "Write correct recursive solution. Add memoization to make it fast."