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$
$\endgroup$
-
$\begingroup$ Try to write dp recursive relation. $\endgroup$ – Eugene Mar 20 '18 at 17:36
-
$\begingroup$ @Eugene could you give some hints? $\endgroup$ – trill.o.beat Mar 20 '18 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 '18 at 18:21
-
$\begingroup$ cs.stackexchange.com/tags/dynamic-programming/info $\endgroup$ – D.W.♦ Mar 20 '18 at 21:42
