如何从递归函数获取数据？

Question

我已经创建了一个递归函数，它返回最好的价格，您可以在市场上销售苹果。由于在现实世界中解释这个问题要简单得多，所以我将在买家和苹果上解释它。

有三位买家。每个买家愿意为不同的苹果支付不同的价格。

必须有3*n苹果，因为你必须向所有（三）买家出售相同数量的苹果。

该功能找到最佳销售。

例如：apples = [[1,50,1], [1,50,1], [1,1,50]]意味着有三个买家和三个苹果。

第一个苹果（apples[0]）可以卖给第一个买家（apples[0][0]）1美元，第二个买家为50美元，第三个买家为1美元。

（函数返回101这是正确的，你不能分发这些三个苹果赚更多的钱）

此功能强大，而且其计算结果（你赚了多少钱）。我想知道哪个苹果我必须卖给哪个买家才能赚取最高的金额。它在某处，但我无法弄清楚如何从函数中获得它，因为它是递归的，直到递归不在最后一级，你不知道你需要计算哪些结果。

apples = [[1,50,1], [1,50,1], [1,1,50]] 

def sell_apples(buyer1, buyer2, buyer3): 
    global results 
    if (buyer1,buyer2,buyer3) in results.keys(): 
     return results[(buyer1,buyer2,buyer3)] 

     n = sum([buyer1, buyer2, buyer3]) 
     if buyer1 == buyer2 == buyer3 == 0 or n == 0: 
      return 0 
     os = [] 
     for i in range(3): 
      buyers = [buyer1, buyer2, buyer3] 
      if buyers[i] > 0: 
       buyers[i] -= 1 
       os.append(sell_apples(*buyers) + apples[n - 1][i]) # here are possible parts of results 
     m = max(os) 
     results[(buyer1,buyer2,buyer3)]=m 
     return m 


print sell_apples(1,1,1) 

返回101，这是正确的。但我想要得到这样的结果：[(0,1),(1,0),(2,2)]这意味着当你将第一个苹果卖给第二个买家，第二个苹果卖给第一个买家，第三个苹果卖给第三个买家时，你有最好的结果。

它可以以某种方式从apples[n-1][i]获得，但这里有所有的选项，不只是我想要的。

Answer 1

或许递归并不是解决这个问题的最好方法，因为如果重新计算中间结果，看起来会有很多。缓存这些结果可以缓解这个问题。相反，您可以尝试从底部构建问题，首先计算较小问题的最佳结果并将其保存在表格中。由于您将结果保存在表格中，因此跟踪最终解决方案而不仅仅是分数也会更容易。

有趣的是，这种保持中间结果的自下而上的方法被称为“动态编程”，你在标签中提到，但不要在你的程序中使用。对于动态编程算法有一些很好的例子，例如对于背包问题或维特比算法和（对于一个非常基本的例子）计算斐波纳契数。

快速解决您的问题将是每次从功能返回时跟踪买家配置。