Here is the question:

You are doing the Tour de France and you are given a map with all the n places where you can refill your water bottles. Your bottles fit 2 liters of water with which are enough for m kilometres. Your goal is to stop as few times as possible to refill your bottles, since you care about a good time for the Tour de France. Design an efficient algorithm using dynamic programming, prove its correctness and analysis its run time. Give the one-dimensional array A. And the time complexity of filling your array.

I just confuse about this question. And what is the motivation to use dynamic programming.I think it looks like bin packing problem without change the order of choice. Why not use greedy next fit approach(e.g refill at kth station if we can't reach k+1th station without refill)could someone give some hint? Thanks

  • $\begingroup$ Because dynamic programming returns optimal solution, don't you think so? $\endgroup$ – rus9384 Sep 13 '17 at 23:49
  • $\begingroup$ @rus9384 I have no idea right now how to do it with dp , but why is the greedy do not get optimal. $\endgroup$ – hahahaha Sep 14 '17 at 0:03
  • $\begingroup$ You could try to find counterexample. This problem is probably not in $\mathsf P$. $\endgroup$ – rus9384 Sep 14 '17 at 0:17
  • $\begingroup$ Do you have a proof that your greedy algorithm always returns the optimal answer? Have you tried testing it with random testing (see cs.stackexchange.com/q/59964/755)? $\endgroup$ – D.W. Sep 14 '17 at 0:19

The most common reason not to use a greedy algorithm is if it wouldn't return the optimal solution on the problem you care about.

Presumably they suggest you use dynamic programming because it is possible to solve it that way, and/or they think that solving it using dynamic programming will be useful practice that will help you learn how to build dynamic programming algorithms.

  • $\begingroup$ Give some proofs for cases where greedy cannot work. $\endgroup$ – Madhusoodan P Sep 14 '17 at 2:15
  • $\begingroup$ @MadhusoodanP There are several questions on this site exploring this challenge. There are several definitions of greedy algorithms, and they can be used to show that in some cases indeed greedy algorithms don't work. $\endgroup$ – Yuval Filmus Sep 14 '17 at 6:48
  • $\begingroup$ @YuvalFilmus Sir then it's better to close the question. right? $\endgroup$ – Madhusoodan P Sep 14 '17 at 16:01

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.