动态规划问题

Question

嗯，我真的不需要代码本身的帮助，但是我明白我到底想要做什么来编写代码。简单地说，我得到了1000个项目，每个项目都有一组资源，我有一组资源可以用来计算我能选择的最好的项目。

最佳利润函数的伪码如下：

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

当我对bestProfit进行递归调用时，best1应该检查子问题是否已经解决。而best2，考虑的可行性检查只是基于最后一个项目。换句话说，它看起来像一棵平衡的树。我无法理解的是如何在递归期间将值插入到映射中？基本上，在遍历完整个项目集之前，最后的if/ set语句是不会发生的。只有最后的值才会被插入到我的地图上。我只想知道我应该如何处理这个问题，以便正确地编写递归。

正如我之前所说的，我并不是在寻找代码，而是一种理解C++项目中伪代码的需求的方法。在这一点上，正是这种逻辑让我抓狂，因为我不能把它放在一起工作。感谢大家的关注，如果可能的话提供更好的洞察力。

Answer 1

我会返回一个数据结构，它同时表示利润和获得利润的解决方案。将准确的数据结构存储在valueMap中。这将使您的代码更加直观。

基本上，“编写正确的递归解决方案。添加回忆录使其快速。”

Answer 2

你不用自下而上的解决方案吗？

它是背包问题的一个直接应用，具有众多的启发式，适用于在分数可能的情况下使它成为一个贪婪的解。

对于您的问题，重复的是让W->某个概念来定义您的资源是否足以满足

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

递归不好，不允许使用普通函数调用进行许多编译器优化。