java - 如何通过设计贪心算法来编写解决此问题的 Java 代码？

Question

问题：

你要去长途旅行。您从 0 英里路段开始上路。沿途有 n 家旅馆，编号为 1 ≤ i ≤ n，英里路段 a 1 < a 2 < 。. . < an ，其中每个 ai 都是从起点开始测量的。您唯一可以停留的地方是这些酒店，但您可以选择在哪家酒店停留。您必须在最后一家酒店（距离为 ）停留，这是您的目的地。理想情况下，您希望每天旅行 200 英里，但这可能是不可能的（取决于酒店的间距）。如果您在一天内行驶 x 英里，则当天的罚款为 (200 − x) 2 。您希望计划您的旅行，以最大限度地减少总罚款，即每日罚款的总和。

有谁知道我如何编写一个通过使用贪心算法来解决这个问题的 Java 代码？

我已经拥有的是：

public static void greedy(int[] a) {
    int[] hotel = a;
    int[] cost = new int[hotel.length];
    int[] stop = new int[hotel.length];

    int dist = 0;

    for (int i = 0; i < hotel.length - 1; i++) {
        dist = a[i + 1] - a[i];
        cost[i] = (int) (Math.pow((200 - hotel[i]), 2));
        stop[i] = 0;
    }
}

但我不知道从这里去哪里..

标签： javaalgorithmgreedy

Answer 1

a(n)据我所知，您需要覆盖的总距离是。由于我们必须住在最后一家酒店，所以我想提出一个反向模式的贪婪解决方案。

如果a(n) - a(n-1)不能大于200英里。所以我想选择一家a(i)介于a(n)和之间的酒店a(n) - 200。现在我们正在考虑一种贪婪的方法，您需要选择该酒店并将该酒店保存在您的访问列表中。

现在，从那里继续前进，然后选择距离之间的下一家酒店，a(i)依此a(i) - 200类推，直到您到达起点。

我没有写任何代码，因为我认为这是家庭作业。不过，我想你明白了。希望有帮助！祝你好运。