成本计算递归求解产品的总成本

wodewan

飞天篮球猪 发表于 2024-3-10 09:40
大佬，这样递归了多少次？（12次还是16次）
A002和A001有重复的分支，实际上A001遍历完之后，很多中间件 ...

大佬考虑的很周全，如果是针对单个产品的（不存在重叠子问题），但按题目要求求所有产品（包括中间件），因为最后一行是循环取数的，所以存在重叠子问题。

飞天篮球猪

wodewan 发表于 2024-3-10 09:50
大佬考虑的很周全，如果是针对单个产品的（不存在重叠子问题），但按题目要求求所有产品（包括中间件）， ...

口算了一下   单个产品比如只计算A001，应该是8次，所以单独计算A002也是8次，这样就是16次
如果在计算A002的时候利用A001时已经算好的中间件，可以减少B001这个分支的4次。
这种BOM往往很多分支，能减少中间过程递归会对效率有助益。不知道对不对，哈哈。

Again123456

飞天篮球猪 发表于 2024-3-10 10:03
口算了一下   单个产品比如只计算A001，应该是8次，所以单独计算A002也是8次，这样就是16次
如 ...

我也想过这个问题，一开始以为要倒了算。

飞天篮球猪

Again123456 发表于 2024-3-10 11:12
我也想过这个问题，一开始以为要倒了算。

JS可以"备忘录递归"，设定一个全局变量Cache={}，用于存储中间件的结果，也可以当成最终结果。
这样的话A001计算完之后，A001这条路径上的所有分支都记录在Cache里了，当计算A002的时候，一样的分支可以直接在Cache里引用得到，不用再递归一遍。供参考....

wodewan

飞天篮球猪 发表于 2024-3-10 11:44
JS可以"备忘录递归"，设定一个全局变量Cache={}，用于存储中间件的结果，也可以当成最终结果。
这样的话 ...

飞天篮球猪

wodewan 发表于 2024-3-11 09:13

大佬，是不是只要遍历产品中的两个顶级就可以了A001和A002？ 然后dic就是结果了。

wanghan519

飞天篮球猪 发表于 2024-3-10 11:44
JS可以"备忘录递归"，设定一个全局变量Cache={}，用于存储中间件的结果，也可以当成最终结果。
这样的话 ...

意思是不是python里的@functools.cache装饰器

wodewan

飞天篮球猪 发表于 2024-3-11 09:59
大佬，是不是只要遍历产品中的两个顶级就可以了A001和A002？ 然后dic就是结果了。

是的

飞天篮球猪

wanghan519 发表于 2024-3-11 10:31
意思是不是python里的@functools.cache装饰器

大佬，python我不会。但python肯定可以写备忘录递归，主要是用来减少子过程的重复。相当于是剪枝了。
只要能设定全局变量的，都可以写。

wodewan

wanghan519 发表于 2024-3-11 10:31
意思是不是python里的@functools.cache装饰器

其实就是个用个字典记录每层递归的结果（也就是每层栈函数调用的结果），好像也叫什么记忆化搜索，因为递归可能存在重复的子问题，这样搜过的就不用搜了。