2

I've created a function about which I though that it is a dynamic programming approach but I've found out that DP can be Bottom-Up but this function is Top-Down. Now, I'm trying to convert this function to Bottom-Up. Do you guys have any hints?

There are 3*n apples (3,6,9.. or 81..) and 3 buyers. Each buyer is able to buy each apple for different price. The input is a list (apples) of prices. [[1,2],[4,5]] means that the first apple can be sold for 1$ to first buyer and for 2$ to second buyer.

The function returns the best price you can earn.

The only thing I want is to convert it from Top-Down to Bottom-up so I can use dynamic programming but I have no success.

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 Bottom-Up approach: (this is as far as I get)

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
Cœur
  • 37,241
  • 25
  • 195
  • 267
Lemmy
  • 59
  • 6
  • In fact, I just want to ask how to create the bottom-up function from the function above. I do understand bottomup for fibonacci but I can't do anything with this function./ – Lemmy Apr 24 '16 at 15:40
  • What makes you think the first approach is top-down? What part of the process are you re-computing or what is the "smaller problem"? – OneCricketeer Apr 24 '16 at 15:50
  • the sell_apples(b1,b2,b3) is a maximum of sell_apples(b1-1,b2,b3)+price_of_the_nth_apple_for_first_buyer, sell_apples(b1,b2-1,b3)+price_of_the_nth_apple_for_second_buyer+sell_apples(b1,b2,b3-1)+price_of_the_nth_apple_for_third_buyer – Lemmy Apr 24 '16 at 15:52
  • It calls the function from the top (sell_apples(3,3,3)) to the bottom parts (sell_apples(0,0,0)) So that's why I think it's top-down. The main thing I want is to make it DP. – Lemmy Apr 24 '16 at 15:54
  • For memoized Fibonacci, `fib[n] = fib[n-1] + fib[n-2]` is considered bottom-up while the function call version without memoization is considered top-down. Your first version appears to be memoized, so wouldn't that be bottom-up since you are obtaining the results from the bottom instead of calculating them at the top of the recursive call stack? – OneCricketeer Apr 24 '16 at 16:00
  • I would suggest cleaning up your top-down algorithm to not use globals, to use a list of apples instead of hardcoding in 3 apples, and to use better practices before trying to do anything else. There is a lot of cruft in the code that makes it hard to reason about. – gnicholas Apr 24 '16 at 16:07
  • I've read articles that the DP is only Bottom-Up and the second approach is Top-Down which is with memoization but it's not a DP. Like in this answer. http://stackoverflow.com/a/6164748/3371056 – Lemmy Apr 24 '16 at 16:10
  • @Lemmy the top-down and bottom-up approaches are two sides of the same coin. Often the top-down approach is more natural to implement, as it is straight recursion with memoization, while the bottom-up approach tends to be more efficient, as it uses explicit iteration and doesn't use stack frames from recursion. – gnicholas Apr 24 '16 at 16:13
  • But I have to use DP approach, It's excersise I can't figure out for days. – Lemmy Apr 24 '16 at 16:37
  • I don't know whether I started good. I'm trying to figure out what iteration should I put there. While loop is not a good idea probably. Maybe for i in range(n). – Lemmy Apr 24 '16 at 16:43
  • Can you please describe your top-down algorithm in words in the body of your question? – גלעד ברקן Apr 24 '16 at 17:29

0 Answers0