c++ - 动态规划问题

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，认为可行性检查仅基于最后一个项目。换句话说，它看起来像一棵平衡树。 我无法理解的是如何在递归期间在 map 上插入值？基本上，在遍历整个项目集之前，不会出现最终的 if/else 语句。并且只有最终值被插入到我的 map 上。 我只想要一些关于我应该如何处理它以正确编写递归的指示。

就像我之前说的，我不是在寻找代码，而是在寻找一种方法来理解这个伪代码对我的 C++ 项目的要求。正是这种逻辑让我在这一点上发疯，因为我无法将它们组合在一起工作。 感谢大家查看此内容并在可能的情况下提供更好的见解。

Answer 1

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

基本上，“编写正确的递归解决方案。添加内存以使其更快。”