2

我创建了一个函数，我认为它是一种动态编程方法，但我发现它DP可以是自下而上的，但这个函数是自上而下的。现在，我正在尝试将此函数转换为Bottom-Up. 各位有什么提示吗？

有3*n苹果（3,6,9.. 或 81..）和 3 个买家。每个买家都可以以不同的价格购买每个苹果。输入是价格列表（苹果）。[[1,2],[4,5]]意味着第一个苹果可以以 1 美元的价格卖给第一个买家，以 2 美元的价格卖给第二个买家。

该函数返回您可以获得的最佳价格。

我唯一想要的是将它从 to 转换为Top-Down，Bottom-up以便我可以使用动态编程，但我没有成功。

apples = [[1,50,1], [1,50,1], [1,80,50]] (3 apples for example)

results = {}

def sell_apples(buyer1, buyer2, buyer3):
    global results
    if (buyer1,buyer2,buyer3) in results.keys(): # memoization
        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])
    m = max(os)
    results[(buyer1,buyer2,buyer3)]=m # memoization
    return m

DP 自下而上的方法：（据我所知）

def sell_apples_bottom_up(buyer1,buyer2,buyer3):
        n = sum([buyer1, buyer2, buyer3])
        def sabu(buyer1,buyer2,buyer3):
            if all(x==0 for x in [buyer1,buyer2,buyer3]):
                return 0
            os = []
            for i in range(3):
                buyers = [buyer1,buyer2,buyer3]
                if buyers[i]>0:
                    buyers[i] -= 1
                    os.append(sabu(*buyers))
            m = max(os)
            return m
       # LOST HERE
4

0 回答 0