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