再帰関数からデータを取得する方法は？

Question

私はあなたが市場でリンゴを販売することができる最高の価格を返す再帰関数を作成しました。現実世界でこの問題を説明するのははるかに簡単なので、私はバイヤーとリンゴについて説明します。

3人のバイヤーがいます。各買い手は、異なるリンゴの異なる価格を支払う意思があります。

すべての（3人の）買い手に同じ量のリンゴを販売しなければならないので、3*nリンゴが必要です。

この関数は、可能な限り最高の売り上げを見つけます。

たとえば、apples = [[1,50,1], [1,50,1], [1,1,50]]は、購入者が3人、リンゴが3人であることを示します。

最初のリンゴ（apples[0]）は、1ドル、1ドル、2ドル、50ドル、3番の買い手に1ドルで売ることができます（apples[0][0]）。

（関数が正しいである101を返し、あなたがより多くのお金を稼ぐこれらの3個のリンゴを配布することはできません）

この機能は素晴らしい作品が、それは（あなたが得るどのくらいのお金）の結果をカウントします。最大限のお金を稼ぐために、どの買い手に売る必要があるのか​​知りたいです。それはどこかにありますが、再帰的で再帰が最後のレベルにならないうちに、どの結果を数えなければならないかわからないので、関数からそれを取得する方法を理解できません。

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)]これは、第1のリンゴを第2のバイヤー、第2のリンゴを第1のバイヤーに販売し、第3のリンゴを第3のバイヤーに販売するときの最良の結果を意味する。

これは何とかapples[n-1][i]から取得できますが、必要なものだけでなく、ここにすべてのオプションがあります。

Answer 1

おそらく再帰は、中間結果が再計算された場合にたくさんあるように見えるので、この問題を解決する最善の方法ではないでしょう。これらの結果をキャッシュすることで、この問題を緩和しました。その代わりに、問題のボトムアップを試みることができます。最初に小さな問題の最良の結果を計算し、それらをテーブルに保持することができます。結果をテーブルに保存するので、スコアだけでなく最終的なソリューションを追跡することも簡単になります。

おもしろいことに、中間結果を保持するこのボトムアップのアプローチは「ダイナミックプログラミング」と呼ばれ、タグで言及しますが、プログラムでは使用しません。動的プログラミングアルゴリズムについては、いくつかの良い例があります。ナップザック問題またはビタビアルゴリズムのために（そして非常に基本的な例として）フィボナッチ数を計算する。

問題をすばやく解決するには、関数から返されるたびに購入者の設定を把握する必要があります。