Пожалуйста, подпишитесь на официальный канал Codeforces в Telegram по ссылке https://t.me/codeforces_official. ×

How to think of locally optimal solution in greedy?

Правка en4, от ay2306, 2018-07-02 13:41:16

I studied about greedy algorithms and found that all we have to do is try a locally optimal solution and hope it turns out to be globally optimal. But my problem is how to find a locally optimal solution when logic I am developing is already taking global optimal solution.

For example, I was working on some greedy example and came across this question. In this question my local optimal approach was that I will check if Current fuel can travel out of the forest, if not then refuel but then it bombed me with a limitation of availability fuel at a stop so I was now deep struck into thinking how to solve it. So doesn't this require a solution where local optimal won't work because we need to have a knowledge of all stops and amount of fuel they require

As in,

Let's say we were at a stop which can provide 2 unit fuel and we have 4 units of fuel, and two other stops are at distance 2 unit each consecutively, but next one provides 100 units fuel(which can cover whole travel) and one after that makes me stop.

So what should be the local optimal solution approach here, because I am unable to find any without taking the whole scenario into account?

Теги greedy, unable to understand, approach

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en4 Английский ay2306 2018-07-02 13:41:16 1 Tiny change: 'e\n\nAs in\n\nLet's ' -> 'e\n\nAs in,\n\nLet's '
en3 Английский ay2306 2018-07-02 06:56:50 0 Tiny change: 'EXPEDI/). How in this que' -> 'EXPEDI/). In this que'
en2 Английский ay2306 2018-07-02 06:56:03 6 Tiny change: 'EXPEDI/). How in this que' -> 'EXPEDI/). In this que'
en1 Английский ay2306 2018-07-01 20:23:41 1263 Initial revision (published)