贪心算法证明如下.doc

贪心算法证明如下 设定如下变量 Value[i]第i个加油站的油价 Over[i]在第i站时的剩油 Way[i]起点到油站i的距离 X[I]X记录问题的最优解X[I]记录油站I的实际加油量 首先X[1]0Over[1]=0 假设第I站加的X[I]一直开到第K站则有X[I].x[k-1]都为0而X[K]0 若Value[I]>Value[k]则按贪心方案第I站应加油为 T=Way[k]-Way[I]