提高题二： 汽车加油问题

 

一、实验目的与要求

1、掌握汽车加油问题的算法；

2、进一步掌握贪心算法；

二、实验题

     一辆汽车加满油后可以行驶N千米。旅途中有若干个加油站。若要使沿途的加油次数最少，设计一个有效的算法，指出应在那些加油站停靠加油。并证明你的算法能产生一个最优解。

三、实验提示

把两加油站的距离放在数组中，a[1..n]表示从起始位置开始跑，经过n个加油站，a[k]表示第k－1个加油站到第k个加油站的距离。汽车在运行的过程中如果能跑到下一个站则不加油，否则要加油。

 

三、源代码

 

1. import java.util.*; 
2.  
3. import java.io.*; 
4.  
5.   
6.  
7.   
8.  
9. public class SF_QicheJiayouzhan 
10.  
11. { 
12.  
13.        public static int greedy(int x[],int n){ 
14.  
15.               int sum=0, 
16.  
17.                      k=x.length, 
18.  
19.                      s=0; 
20.  
21.               for (int j=0;j<k ;j++ ) 
22.  
23.               { 
24.  
25.                      if (x[j]>n) 
26.  
27.                      { 
28.  
29.                             System.out.println("无法到达目的地！！！"); 
30.  
31.                             return -1; 
32.  
33.                      } 
34.  
35.                      
36.  
37.               } 
38.  
39.               for (int i=0;i<k ;i++ ) 
40.  
41.               { 
42.  
43.                      
44.  
45.                      s+=x[i]; 
46.  
47.                      if (s>n) 
48.  
49.                      { 
50.  
51.                             sum++; 
52.  
53.                             s=x[i]; 
54.  
55.   
56.  
57.                             } 
58.  
59.                      } 
60.  
61.               return sum; 
62.  
63.        } 
64.  
65.        public static void main(String[] args) 
66.  
67.        { 
68.  
69.               Scanner read =new Scanner(System.in); 
70.  
71.               System.out.println("请输入汽车加满油一次最大行驶旅程："); 
72.  
73.               int n=read.nextInt(); 
74.  
75.               System.out.println("请输入加油站个数："); 
76.  
77.               int num=read.nextInt(); 
78.  
79.               int a[]=new int[num]; 
80.  
81.               System.out.println("请输入每个加油站的相隔距离："); 
82.  
83.               for (int i=0;i<num ;i++ ) 
84.  
85.               { 
86.  
87.                      a[i]=read.nextInt(); 
88.  
89.               } 
90.  
91.               int q=greedy(a,n); 
92.  
93.               System.out.println("要加油"+q+"次。"); 
94.  
95.        } 
96.  
97. } 

结果：

 

本文转自 梦朝思夕 51CTO博客，原文链接:http://blog.51cto.com/qiangmzsx/824850