汽车加油问题 一辆汽车加满油后,可行使n千米。旅途中有若干个加油站。若要使沿途加油次数最少,设计一个有效算法，对于给定的n和k个加油站位置，指出应在哪些加油站停靠加油才能使加油次数最少。 实验提示： 把两加油站的距离放在数组中，a[1..k]表示从起始位置开始跑，经过k个加油站，a[i]表示第i－1个加油站到第i个加油站的距离。汽车在运行的过程中如果能跑到下一个站则不加油，否则要加油。

问题描述 一辆汽车加满油后可以行驶nkm。旅途中有若干加油站。设计一个有效算法指出应在哪些加油站停靠加油，使沿途加油次数最少。

贪心算法、回溯算法、动态规划算法等思想实现的加油问题

题目来源：王晓东《算法设计与分析》 一辆汽车加满油后可行驶 n公里。旅途中有若干个加油站。设计一个有效算法，指出应 在哪些加油站停靠加油，使沿途加油次数最少。 输入格式: 第一行有 2 个正整数n和 k（k<=1000 )，表示汽车加满油后可行驶n公里，且旅途中有 k个加油站。 第二行有 k+1 个整数，表示第 k 个加油站与第k-1 个加油站之间的距离。 第 0 个加油站表示出发地，汽车已加满油。 第 k+1 个加油站表示目的地。 输出格式: 输出最少加油次数。如果无法到达目的地，则输出“No Solution!”。 输入样例: 7 7 1 2 3 4 5 1 6 6 输出样例: 4

贪心算法解汽车加油问题实验报告 分析 代码 复杂度 心得体会 比较齐全

虚拟汽车加油问题C++.txt

实现4-9汽车加油问题.cpp

给定一个N*N 的方形网格，设其左上角为起点◎，坐标为（1，1），X 轴向右为正，Y轴向下为正，每个方格边长为1，如图所示。一辆汽车从起点◎出发驶向右下角终点▲，其坐标为（N，N）。在若干个网格交叉点处，设置了油库，可供汽车在行驶途中加油。汽车在行驶过程中应遵守如下规则： 　　　(1)汽车只能沿网格边行驶，装满油后能行驶K 条网格边。出发时汽车已装满油，在起点与终点处不设油库。 　　　(2)汽车经过一条网格边时，若其X 坐标或Y 坐标减小，则应付费用B，否则免付费用。 　　　(3)汽车在行驶过程中遇油库则应加满油并付加油费用A。 　　　(4)在需要时可在网格点处增设油库，并付增设油库费用C（不含加油费用A）。 　　　(5)(1)～(4)中的各数N、K、A、B、C均为正整数，且满足约束：2 ≤ N ≤100，2 ≤ K ≤10。设计一个算法，求出汽车从起点出发到达终点的一条所付费用最少的行驶路线。