Dynamic Programming Problem

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 follo开发者_开发问答ws:

bestProfit:

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."

---

Y u no use a a bottoms up solution?

It is a straight forward application of Knapsack problem with numerous heuristics applicable to making it a greedy solution if fractions are possible...

For your problem the recurrence is Let W-->some notion by which you define if your resources are adequate enough for a
problem 'k' Let N --> set of problems indexed by a 0-index Let V --> 0 based index of potential profit for solving each problem OPT[i][j] = MAX( OPT[i-1][j], OPT[i-1][j-W[i]]+V[i]) where 'i' is the an index into the list of problems. j is an index into how much resources are available yet. Your solution is then OPT[size[N]][W] Explanation: Intuitively, the sub problem is choosing the optimal set of projects among 'i' with available resources 'j'...

Recursion is bad doesnt allow many compiler optimizations possible with normal function calls.