动态规划问题
好吧,我真的不需要代码本身的帮助,而是了解我到底想要做什么来编写代码。简而言之,我有 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 技术交流群。
发布评论
评论(2)
您没有使用自下而上的解决方案吗?
这是背包问题的直接应用,如果分数是可能的,则可以使用许多启发式方法使其成为贪婪的解决方案......
对于您的问题,递归是
让 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”中选择最佳的项目集...
递归很糟糕,不允许通过正常的函数调用进行许多编译器优化。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
我将返回一个数据结构,该数据结构指示利润和获得该利润的解决方案。将确切的数据结构存储在
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."