跳转至

贪心法确定补水地点

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <iostream>

using namespace std;

const int N = 17;  //水站的个数 

//贪心法选择在哪一个水站加水，d[]储存每个水站距离起点的距离，f[]标记相应的水站是否需要加水(0-不加，1-加) 
void greedy_fillup(float d[], int f[]) { 
    float maxDistance = 1; //最初水箱满时可以走1英里 
    for (int i = 2; i <= N; i++) { //从第2个水站扩展到最后一个水站 
        if (d[i] > maxDistance) { //如果某个水站的距离起点的距离大于当前能走的最远距离，则在前一站加水 
            f[i - 1] = 1;         //标记前一站需要加水
            maxDistance = 1 + d[i - 1]; //改变当前能走的最远距离，因为在第i-1站已经加过水，则在第i-1站的距离上加1 
        }
    }
}

//根据f[]和d[]打印最优解 
void print_opitimal_solution(float d[], int f[]) { 
    for (int i = 1; i <= N; i++) {
        if (f[i] == 1) {
            cout << "The refilling location "<< i << " is chosen, and its distance is " << d[i] << endl;    
        }
    }
}

int main() {
    //d[i]表示第i个水站距离起点的距离 
    float d[N + 1] = {0, 0.7, 1.2, 2.1, 2.9, 3.6, 3.9, 4.9, 5.1, 5.5, 6.0, 7.0, 7.7, 8.2, 9.1, 9.9, 10.2, 11};
    //f[i]标记第i个水站是否加水，0-不加，1-加
    int f[N + 1] = {0};
    greedy_fillup(d, f);
    print_opitimal_solution(d, f);
    return 0;
}