有一个城镇网络,由各种整数长度的道路连接。
一位旅行者希望开车从一个城镇到另一个城镇。但是,他不想最小化行驶的距离;相反,他希望尽量减少旅途中的汽油费用。汽油可以在任何城市购买,但是每个城市以不同的(整数)价格供应汽油(因此为什么最短的路线不一定是最便宜的)。1 个单位的汽油使他能够行驶 1 个单位的距离。他的车只能在油箱里装这么多汽油,他可以选择在他所经过的每个城市购买多少单位的汽油。找出最低的汽油成本。
有谁知道可以用来解决这个问题的有效算法?即使是这类问题的名称也会很有用,这样我就可以自己研究了!显然,它与最短路径问题并不完全相同。任何其他提示表示赞赏!
编辑-我遇到的实际问题表明将有<1000个城市;<10000 条道路;油箱容量将在 1 到 100 之间。