[求助]加油问题 求算法思想及程序 求各位务必帮帮忙 感激不尽
假定你要在Ｉ－８０公路上驱车从旧金山到纽约市．你的汽车装有Ｃ加仑汽油，可以行驶m英里．Ｉ－８０公路上n个加油站机器所售汽油的价格的一览表，设di为第i个加油站距离旧金山的距离,ci是在第i个加油站加油的开销．假设对于任意两个加油站i和j，它们之间的距离di-dj为的m倍数．你从加油站１出发时，油箱为空．你的最终目的地为加油站n．在你到达目的地n时，油箱油料至少为０．试设计一多项式时间动态规划算法，输出穿过这段公路所需的最小汽油量．并根据n和Ｃ，分析你所设计的算法的运算时间．
需注意的是，当油箱中的汽油量小于０时，汽车不能行驶；当你决定在某站加油时，也不必加满油箱．
我希望有人能够提供一些思路给我，我不需要程序，我只想要过程。
动态规划的过程。谢谢了。
[此贴子已经被作者于2007-10-31 21:18:41编辑过]
