动态规划问题

发布于 11-03 19:29 字数 1626 浏览 4 评论 0原文

好吧,我真的不需要代码本身的帮助,而是了解我到底想要做什么来编写代码。简而言之,我有 1000 个项目,每个项目都有一组资源,并且我有一组(一组)资源可用来计算我可以选择的最佳项目。

bestprofit 函数的伪代码如下:

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/else 语句不会发生。并且只有最终值会插入到我的地图上。 我只是想要一些关于如何正确编写递归的指导。

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

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:

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.

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(2

司马昭之心2024-11-10 19:29:19

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

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

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

栖迟2024-11-10 19:29:19

您没有使用自下而上的解决方案吗?

这是背包问题的直接应用,如果分数是可能的,则可以使用许多启发式方法使其成为贪婪的解决方案......

对于您的问题,递归是
让 W--> 一些概念,您可以通过它来定义您的资源是否足以满足
问题“k”
设 N -->由 0 索引索引的问题集
令 V -->解决每个问题的潜在利润的基于 0 的指数
OPT[i][j] = MAX( OPT[i-1][j], OPT[i-1][jW[i]]+V[i]) 其中 'i' 是索引
问题清单。 j 是可用资源数量的索引。
那么你的解决方案是 OPT[size[N]][W]
解释:
直观地说,子问题是在具有可用资源“j”的“i”中选择最佳的项目集...

递归很糟糕,不允许通过正常的函数调用进行许多编译器优化。

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.

~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文