Mr. Katsaros owns a rectangular olive grove divided into 5 rows and 4 columns. He notes down the amount of olives (pounds) possibly obtainable from each of 20 square sections. The picking starts from the furthest north-west section and ends in the furthest south-east section. What is the maximal amount of olives that can be picked at one go if the pickers can only go directly south or directly east? Implement your algorithm using C++.

I think the right method incorporates dynamic programming. I guess the rectangular note has to be transformed into a directed graph but I don't know how. I was thinking about attributing amount from a section to the edges leading to the corresponding vertices and using Ford-Fulkerson algorithm. However, I don't know if that is the correct approach and how to implement it.

  • $\begingroup$ Try to write dp recursive relation. $\endgroup$
    – Eugene
    Mar 20, 2018 at 17:36
  • $\begingroup$ @Eugene could you give some hints? $\endgroup$ Mar 20, 2018 at 17:53
  • $\begingroup$ Consider a cell. Suppose you know the maximum amount of olives he can collect from either its west or north. What can you say about this cell? Why does it work?(he can’t go back). What’s the maximum amount he can collect if finishing in the starting cell? $\endgroup$
    – Eugene
    Mar 20, 2018 at 18:21
  • $\begingroup$ cs.stackexchange.com/tags/dynamic-programming/info $\endgroup$
    – D.W.
    Mar 20, 2018 at 21:42


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.