java - 我如何改变这个贪心算法来预测最全面的分数？

Question

大家好，这是我在这里的第一篇文章。

所以今天在我的大学类里面，我们的教授给了我们一个编写算法的任务:

编写一个函数，返回为了在棋盘游戏中获得最高分而需要走的步数:

游戏规则:

• 你掷一个骰子并相应地移动(1-6 步)。
• 棋盘上的方 block 数量可以介于 2 - 99 999 之间。
• 当您踩到一 block 瓷砖时，您会获得或失去分数(每 block 瓷砖上的分数从 -99 999 到 99 999 不等)。
• 如果您在棋盘的末端，并且您掷出的骰子超出了边界，您就不要移动。

我的方法

这是一种贪心算法:

• 如果大于或等于 0，则对每一步进行计数，
• 如果为负，检查接下来的 6 个方 block 并移动到得分最高的方 block ，以减少最少的分数。

在我想象这个例子之后，我意识到我的方法是错误的:

想象一下 {1, -40, -40, -40, -40, -1, -38, -40, -40, -40, -40, -40, 1} 的数组

我的贪心算法从 1 开始，看到四个 -40、一个 -38 和一个 -1。它选择 -1 是因为它是最佳选择，但现在我们将得到以下结果:1 + (-1) + (-38) + 1 = -37，但是如果我们选择 -38 而不是 -1，我们最终会是:1 + (-38) + 1 = -36。

这只是一个可能出现问题的简单示例，我想我必须检查每条可能的路径，因为贪婪算法不会检查那里的最佳路径，只会检查最适用于某些特定的路径时刻。

我想知道是否可以选择包含所有可能性的图，但如果我们有一个只有负数的数组，那么我们最终会得到一个最大尺寸约为 (99999^6?) ，这会导致占用太多内存。

我是一个新手，我的想法已经用完了。谁能指出我正确的方向？

Answer 1

哦，等等!此处使用最大堆可以实现贪心。

想法:

最大堆是一种将最大元素保持在结构顶部的数据结构。如果我们将掷骰子后可能出现的 6 个值保留在最大堆中，我们可以获得骰子可以掷出的最大可能值。

让我们考虑您的示例数组 {1, -40, -40, -40, -40, -1, -38, -40, -40, -40, -40, -40, 1}。

将骰子可以滚动的前六个值压入最大堆。因此，最大堆包含元素 {<1, 0>, <-40, 1>, <-40, 2>, <-40, 3>, <-40, 4>, <-1, 5>} (不在最大堆顺序中)。

在这里<top of the max heap>.value = 1 和 <top of the max heap>.index = 0.

现在，max_score = 1。

弹出最大堆并添加数组中的下一个元素后，最大堆将包含以下元素 {<-40, 1>, <-40, 2>, <-40, 3>, <-40, 4 >, <-1, 5>, <-38, 6>}(不是最大堆顺序)。

同样，您可以使用以下算法计算出输入数组中的剩余元素。

算法:

max_score, curr_index, steps = 0
Push input_array[0..max(5, size_of_input_array - 1)] values in a max heap in the form <value, index in the array>
i = 6

while(max heap is not empty):
    while(max heap is not empty and <top of the max heap>.index < curr_index):
        pop the max heap
    if(max heap is not empty):
        max_score += <top of the max heap>.value
        curr_index = <top of the max heap>.index
        steps++
        pop the max heap
    if(i < size_of_input_array):
        push the <input_array[i], i> into the max heap
        i++
return max_score, steps

Time complexity: O(size_of_input_array * log(6)) => O(size_of_input_array)
Space complexity: O(6) => Constant

没有给出完整的工作代码，因为这是你的任务，但上面的算法不少于代码。

你可以试试Depth First Search , Dynamic Programming以及。但上述贪心解是渐进最有效的方法。

希望对您有所帮助。我喜欢解决它。谢谢!