如何使用设计贪婪算法编写解决此问题的 Java 代码？_java

问题：

你要去长途旅行。 您从 0 英里后的路上开始。沿途有 n 个酒店，编号为 1 ≤ i ≤ n，在 1 英里后有 1 < a 2 < 。 . . < an ，其中每个 ai 都是从起点开始测量的。 您只能在这些酒店停留，但您可以选择停留的酒店。 您必须在最终酒店（距离 a 处）停留，这是您的目的地。 理想情况下，您希望每天旅行 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;
    }
}

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

这个编程问题看起来像是学校的练习。 显然，我们鼓励您自己努力……无论如何，这里有一些提示。

我们首先需要选择一个贪婪算法，即基于某种启发式算法的算法，该算法允许我们基于对下一家酒店的局部最优选择（在每个步骤中执行的选择）来“优化”总费用）。

因此，我们需要给出一个适用于每个步骤的规则，该规则允许我们选择下一家酒店。

作为局部最优选择：我们可以选择每天前进，如果从x点开始，我们将停靠至x+200点附近的下一家酒店。

用某种伪代码：

//start from 0
cost=0
position=0
while(position<end)
    //find the next best hotel h (based on the rule above)
    h=...
    //compute the daily_cost
    daily_cost=(h-position)^2
    //move to the selected hotel
    position=h
    //and increase the total cost:
    total_cost=total_cost+daily_cost

当position=end ：我们已经到达，并且我们已经基于此贪婪算法计算了total_cost 。

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

如果a(n) - a(n-1)不能大于200英里。 因此，我想选择一个位于a(i) a(n)和a(n) - 200之间的中间位置的旅馆a(i) 。 现在，当我们考虑采用贪婪的方法时，您需要选择该酒店并将该酒店保存在您的访问列表中。

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

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

不要向前冲，立即开始编码：从分析任务开始

贪婪意味着采取最佳可能的下一步 （永不回头；向前或向后限制或不允许）。
假设d?是第x天的距离，然后看一下150、200、250英里处的酒店：
-如果费用为200-d?，
总成本为150，第一个距离为200以及150
-如果费用为（200-d?）?，
总成本为22500（第一距离为200），只有12500（150）：
最好让每个绝对差异都尽可能接近所有其他差异
-如果没有（完整的）前瞻，您将不知道所有剩余的内容：
下一个差异应尽可能接近预期平均值
-在其他所有条件相同的情况下，一日游的次数要多于一日游
-提前1天，费用为50和2500的单日旅行成为一种选择。

how I can write a Java code that solves this problem ？
再次研究贪婪并考虑一个（更多）示例（与以往相同）：

请勿写下算法（尚未）：
给测试解决方案认真思考
如果不分析，这是在与任务定义问题势必会成为明显的：是200 miles的上限？ （我可以切换方向吗？）
编写测试代码，使其检查示例任务和结果。 使其标记错误结果 （仅）。
只有这样，才能开始草拟解决方案。
通常，我在这里走弯路/捷径：
我启动了一个源文件（或继续进行测试），并记录了要使用的所选编程工具的文档约定（对于Java）要完成的任务，即。
我在语法上以草图形式轻松地拆分解决方案（Java： //行注释）
检查草绘的解决方案：是否有任何简化说明？
如果看起来很复杂：是否可以放宽限制以允许更简单的方法产生相同的结果？
最终重新实施该方法可能会节省时间，即使重新访问已放弃的限制导致拒绝将其作为解决方案也是如此。
（在这里，是值得一试，如果你的方法看起来显著更加复杂。）
用什么做的如何维护说明，你准备好代码

如何使用设计贪婪算法编写解决此问题的 Java 代码？

问题描述

1楼

2楼

3楼