With Greed-Algorithm thought, here is a ugly implementation of "traveler algorithm".
for each step, I think we can get a best resolution for the traveler. so, the composition of all
sub-resolutions is the best resolution of this problem. the basic idea is using less money for longer trip and the core code is to find out the next gas station where traveler should go.
1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <stdbool.h>
4 /* define gas-station number. */
5 #define N 6
6 /* capacity of the oil box. */
7 double cap = 0;
8 /* distance car moved by every 1 oil-value. */
9 double mov = 0;
10 /* oil added. */
11 double add[N+2];
12 /* array used to store oil-value remained. */
13 double rem[N+2];
14 /* array used to store distance from start point to station. */
15 double dis[N+2];
16 /* array used to stored oil price of gas-station. */
17 double pri[N+2];
18 /* total distance to travel. */
19 double tot = 0;
20
21 void init()
22 {
23 cap = 10; mov = 1; tot = 40;
24 // dis[0] is the start point, so dis[0] is zero.
25 dis[0] = 0;
26 dis[1] = 9; dis[2] = 14; dis[3] = 18; dis[4] = 19; dis[5] = 25; dis[6] = 30;
27 dis[7] = tot;
28 // no price for start point and end point.
29 pri[0] = 0;
30 pri[1] = 10; pri[2] = 6; pri[3] = 8; pri[4] = 2; pri[5] = 4; pri[6] = 2;
31 pri[7] = 0;
32
33 int i = 0;
34 for(i = 0; i < N+2; i++) add[i] = 0;
35 for(i = 0; i < N+2; i++) rem[i] = 0;
36
37 // precondition: beginning, car doesn't need to add any oil.
38 add[0] = 0;
39 // precondition: beginning, car has cap oil.
40 rem[0] = cap;
41 }
42
43 void travel()
44 {
45 init();
46
47 /* reachable station index. */
48 int rcb[N+1];
49 int x = 0;
50 for(x = 0; x < N+1; x++) rcb[x] = 0;
51 /* get reachable station index. */
52 int i = 0;
53 int j = 1;
54 for(x = 0, j = 1; j < N+2; j++)
55 {
56 if(dis[j] - dis[i] <= mov*cap)
57 rcb[x++] = j;
58 else j = N+2;
59 }
60 /* get index of the cheapest station. nxt: next station to go. */
61 int nxt = rcb[0];
62 for(j = 1; j < x; j++) if(pri[rcb[j]] < pri[nxt]) nxt = rcb[j];
63
64 for(i = 1; i < N+1 && nxt < N+1; i++) {
65 puts("/*********************************************************/");
66 /* calculate rem[i]. */
67 rem[i] = rem[i-1] + add[i-1] - (dis[i] - dis[i-1]) / mov;
68 /* just go to the target station and skip this station. */
69 printf("i == %d, rem[%d] == %f and nxt == %d\n", i, i, rem[i], nxt);
70 if(i != nxt) continue;
71
72 /* initialize rcb. */
73 for(x = 0; x < N+1; x++) rcb[x] = 0;
74 /* get all reachable station index. */
75 for(x = 0, j = i+1; j < N+2; j++) {
76 if(dis[j] - dis[i] <= cap*mov) {
77 rcb[x++] = j;
78 printf("rcb[%d] == %d\n", x-1, j);
79 }
80 else j = N+2;
81 }
82 /* get index of the cheapest station. */
83 nxt = rcb[0];
84 for(j = 1; j < x; j++) if(pri[rcb[j]] < pri[nxt]) nxt = rcb[j];
85 printf("nxt == %d\n", nxt);
86
87 if(pri[i] >= pri[nxt]) {
88 printf("pri[%d] >= pri[%d] ", i, nxt);
89 /* find first station having cheaper than pri[i]. */
90 for(x = i+1; x <= nxt; x++) if(pri[i] > pri[x]) break;
91 nxt = x; /* station-x is the first cheaper one. */
92 printf("and nxt == %d now\n", nxt);
93 add[i] = (dis[x] - dis[i]) / mov - rem[i];
94 if(add[i] < 0) add[i] = 0;
95 }
96 else add[i] = cap - rem[i];
97 printf("nxt == %d, add[%d] == %f\n", nxt, i, add[i]);
98 }
99
100 if(nxt < N+1) puts("unreachable!");
101
102 double cst = 0;
103 for(x = 1; x <= N; x++)
104 {
105 if(add[x] == 0) continue;
106 if(add[x] > cap) printf("unreachable! add[%d] == %f > capacity %f\n", x, add[x], cap);
107 cst += add[x]*pri[x];
108 }
109 printf("cost: %f\n", cst);
110 }
111
112 int main()
113 {
114 travel();
115 return 0;
116 }
117
118
The following code are the input data as a demo. they can be changed with your favor.
Please remember to set the macro N in the beginning of the source code file.
cap = 10; mov = 1; tot = 40;
// dis[0] is the start point, so dis[0] is zero.
dis[0] = 0;
dis[1] = 9;
dis[2] = 14;
dis[3] = 18;
dis[4] = 19;
dis[5] = 25;
dis[6] = 30;
dis[7] = tot;
// no price for start point and end point.
pri[0] = 0;
pri[1] = 10;
pri[2] = 6;
pri[3] = 8;
pri[4] = 2;
pri[5] = 4;
pri[6] = 2;
pri[7] = 0;
Running demo image.
