最大化分数的贪心算法
Greedy algorithm to maximize score
我正在尝试在 java 中实现一种方法，该方法将具有截止日期、分数和对象编号的对象 ArrayList 作为输入。每个都可以访问为：
game.get(i).number
game.get(i).score
game.get(i).deadline
其中 game 是 ArrayList，i 是索引。
我想在考虑每场比赛的截止日期的同时最大限度地提高得分。每场比赛必须在截止日期前完成。例如如果截止日期是 5，则必须在 4 或更早完成。
例如，这里有一个示例 ArrayList，其相应数据按分数降序排列：
Index Game number Score Deadline
0 3 76 3
1 4 66 2
2 1 52 2
3 6 51 4
4 5 47 2
5 2 23 1
那么下面的 ArrayList 可能是结果：
maximizedScore = [4,1,3,6] -> 这里每个索引代表小时。尽管第 3 场比赛的得分高于第 4 场比赛和第 1 场比赛，但我们将第 4 场比赛放在索引 0 中，将第 1 场比赛放在索引 1 中，因为它们的截止日期均为 2，因此必须在此之前完成。但是，第 3 场比赛的截止日期为 3，因此我们可以在第 2 小时进行比赛，以最大化总分。请注意，第 5 场比赛也与第 4 场比赛和第 1 场比赛有相同的截止日期，但它的分数比两者都少，所以我们牺牲它。
编辑：每个索引 (0,1,2,3,4,..) 代表小时，而索引处的值代表该小时完成的游戏编号。
编辑 2：我们每小时只能进行一场比赛。因此，如果数据中的最新截止日期是 x，那么我们最多可以进行 x 场比赛。 IE。本例中为 4。
这提供了 245 的最高分数。
只要在截止日期之前，比赛的顺序并不重要。例如：[1,4,3,6] 也可以接受，因为第 4 场和第 1 场比赛都在截止日期前完成。
不幸的是，我不知道如何着手实施它。希望我清楚地说明了我需要什么。
感谢任何帮助！
首先要做的是按照得分对游戏进行排序，因为我们希望得分最高的游戏排在第一位：
如果你有一个 ArrayList 的对象说 ArrayList<Game> inputData = new ArrayList<>(); 你可以在 java:
中这样排序
inputData.sort(Comparator.comparing(Game::getScore));
现在最低分在前，最高分在后。
由于我们必须跟踪截止日期，所以我会将它们放在一个单独的 ArrayList 中，并在需要时将它们一一删除：
ArrayList<Integer> deadlines = new ArrayList<>();
for(Game game : inputData) {
if (!deadlines.contains(game.deadline))
deadlines.add(game.deadline);
}
之后的想法是逐个迭代 inputData 并跟踪 previousDeadline 和 currentDeadline。如果我们认为 currentDeadline 大于 previousDeadline 那么这意味着我们不能接受在此之前的任何截止日期。这可以通过检查我们之前创建的 deadlines 列表并从中删除截止日期来完成。
int previousDeadline = -1; // initial value because there is no -1 deadline
for(int i = inputData.size()-1; i >= 0; i--) {
int currentDeadline = inputData.get(i).deadline;
// compare previous and currentDeadline and remove from deadlines list
if(previousDeadline != -1 && previousDeadline < currentDeadline) {
for(int j = 1; j < currentDeadline; j++) {
deadlines.remove(Integer.valueOf(j));
}
}
// add to result only if present in deadlines list and update previous deadline
if (deadlines.contains(currentDeadline) ) {
result.add(inputData.get(i).number);
previousDeadline = inputData.get(i).deadline;
}
}
如果你给它一个你提供的输入，你会得到一个列表 [3, 4, 1, 6]
我会尝试在不编写任何代码的情况下给出一个通用的方法。
我会把你要找的结果称为“时间表”。正如您在问题中所解释的那样，您可以在日程表中放置的最大游戏数由输入数据的“截止日期”列中的最大值表示。我将其称为“时间限制”。
你问的是贪心算法。这样的算法将生成并检查所有游戏时间表，以找到使您的分数最大化的时间表。
基本方法
您可以采取的最基本的方法是生成长度为“时间限制”或更短的游戏的所有排列。对于其中的每一个，您将检查：
- 它确实是一个有效的时间表吗（暂定时间表中的每场比赛都在放置时支付吗？），
- 这个暂定时间表产生的总分是否高于迄今为止获得的最好分数？如果是这样，您“保留”此解决方案并继续尝试其他时间表
第一种方法的主要困难是正确生成所有可能的时间表。即：
- 0
- 0 1
- 0 1 2
- 0 1 2 3
- 0 1 2 3 4
- 0 1 2 4
- 0 1 2 4 3
- 0 1 3
- .....
- 1
- 1 0
- 1 0 2
- .....
优化
现在，上面的基本方法有一些低效之处。例如，当您正在构建可能的时间表时，您构建了一个由于截止日期标准而无法实现的时间表。例如：
- 3 5
是一个不可能的时间表，因为游戏“5”的截止日期为 1（这意味着它只能作为第一场比赛进行，或者不能全部进行）。如果你能认识到这一点，那么你就会意识到任何以3 5（3 5 0 ...、3 5 1 ...）开头的时间表也是不可能的。
如果您以巧妙的顺序生成计划并跳过您知道不可能的计划的生成，则可以利用这一事实。
算法提示
我建议以递归方式生成时间表。您的所有游戏 ID（0、1 等）都在 collection 中。您从最低索引开始：0，将其从游戏 collection 中删除 并将其放入暂定时间表：
日程安排：0
你检查它是否是一个有效的时间表（即你刚放在你的时间表中的游戏当时是否可以玩）。让我们假设是这种情况（在这种特定情况下，因为它是时间表上的第一场比赛，所以它应该总是可能的）。您还可以检查这个暂定时间表是否比您目前找到的任何时间表产生更好的分数。
然后您尝试添加 collection 剩余游戏中剩余的最低游戏。在这种情况下，1。同样，您从 collection 场比赛中删除 1 并将其列入您的日程安排：
日程安排：0 1
同样的事情，你检查这是否是一个有效的时间表。您已经知道游戏 0 可以先玩，您检查游戏 1 是否可以在第二个位置玩。运气不好，游戏的时间限制1让你无法做到。不再值得探索以 0 1 开头的时间表。您将 1 从您的日程安排中删除，但您不会在比赛中替换它 collection：因为不可能排在第二位，因此不值得进一步检查。相反，我会把它放在 collection 个在当前探索级别被“排除”的游戏中。
然后您继续进行游戏 collection、2 中剩余的下一场游戏并遵循相同的程序。如果您能够将与时间限制兼容的游戏安排在您的日程安排中，您可以继续将游戏添加到您的日程安排中，并保留在游戏 collection 中。请注意，可能存在您完全排满日程但仍有比赛剩余的情况（反之亦然，您的日程安排仍有漏洞但没有比赛可以剩余）。
当您 运行 没有选择时，是时候从日程表中删除游戏了。删除您安排在日程表上的最后一场比赛并将其放回比赛 collection。还将您在当前级别排除的游戏放回游戏 collection 中。您可以继续生成计划。不过，请注意不要再次使用您刚刚在此级别删除的游戏。
我正在尝试在 java 中实现一种方法，该方法将具有截止日期、分数和对象编号的对象 ArrayList 作为输入。每个都可以访问为：
game.get(i).number
game.get(i).score
game.get(i).deadline
其中 game 是 ArrayList，i 是索引。
我想在考虑每场比赛的截止日期的同时最大限度地提高得分。每场比赛必须在截止日期前完成。例如如果截止日期是 5，则必须在 4 或更早完成。
例如，这里有一个示例 ArrayList，其相应数据按分数降序排列：
Index Game number Score Deadline
0 3 76 3
1 4 66 2
2 1 52 2
3 6 51 4
4 5 47 2
5 2 23 1
那么下面的 ArrayList 可能是结果：
maximizedScore = [4,1,3,6] -> 这里每个索引代表小时。尽管第 3 场比赛的得分高于第 4 场比赛和第 1 场比赛，但我们将第 4 场比赛放在索引 0 中，将第 1 场比赛放在索引 1 中，因为它们的截止日期均为 2，因此必须在此之前完成。但是，第 3 场比赛的截止日期为 3，因此我们可以在第 2 小时进行比赛，以最大化总分。请注意，第 5 场比赛也与第 4 场比赛和第 1 场比赛有相同的截止日期，但它的分数比两者都少，所以我们牺牲它。
编辑：每个索引 (0,1,2,3,4,..) 代表小时，而索引处的值代表该小时完成的游戏编号。
编辑 2：我们每小时只能进行一场比赛。因此，如果数据中的最新截止日期是 x，那么我们最多可以进行 x 场比赛。 IE。本例中为 4。
这提供了 245 的最高分数。
只要在截止日期之前，比赛的顺序并不重要。例如：[1,4,3,6] 也可以接受，因为第 4 场和第 1 场比赛都在截止日期前完成。
不幸的是，我不知道如何着手实施它。希望我清楚地说明了我需要什么。
感谢任何帮助！
首先要做的是按照得分对游戏进行排序，因为我们希望得分最高的游戏排在第一位：
如果你有一个 ArrayList 的对象说 ArrayList<Game> inputData = new ArrayList<>(); 你可以在 java:
inputData.sort(Comparator.comparing(Game::getScore));
现在最低分在前，最高分在后。
由于我们必须跟踪截止日期，所以我会将它们放在一个单独的 ArrayList 中，并在需要时将它们一一删除：
ArrayList<Integer> deadlines = new ArrayList<>();
for(Game game : inputData) {
if (!deadlines.contains(game.deadline))
deadlines.add(game.deadline);
}
之后的想法是逐个迭代 inputData 并跟踪 previousDeadline 和 currentDeadline。如果我们认为 currentDeadline 大于 previousDeadline 那么这意味着我们不能接受在此之前的任何截止日期。这可以通过检查我们之前创建的 deadlines 列表并从中删除截止日期来完成。
int previousDeadline = -1; // initial value because there is no -1 deadline
for(int i = inputData.size()-1; i >= 0; i--) {
int currentDeadline = inputData.get(i).deadline;
// compare previous and currentDeadline and remove from deadlines list
if(previousDeadline != -1 && previousDeadline < currentDeadline) {
for(int j = 1; j < currentDeadline; j++) {
deadlines.remove(Integer.valueOf(j));
}
}
// add to result only if present in deadlines list and update previous deadline
if (deadlines.contains(currentDeadline) ) {
result.add(inputData.get(i).number);
previousDeadline = inputData.get(i).deadline;
}
}
如果你给它一个你提供的输入，你会得到一个列表 [3, 4, 1, 6]
我会尝试在不编写任何代码的情况下给出一个通用的方法。
我会把你要找的结果称为“时间表”。正如您在问题中所解释的那样，您可以在日程表中放置的最大游戏数由输入数据的“截止日期”列中的最大值表示。我将其称为“时间限制”。
你问的是贪心算法。这样的算法将生成并检查所有游戏时间表，以找到使您的分数最大化的时间表。
基本方法
您可以采取的最基本的方法是生成长度为“时间限制”或更短的游戏的所有排列。对于其中的每一个，您将检查：
- 它确实是一个有效的时间表吗（暂定时间表中的每场比赛都在放置时支付吗？），
- 这个暂定时间表产生的总分是否高于迄今为止获得的最好分数？如果是这样，您“保留”此解决方案并继续尝试其他时间表
第一种方法的主要困难是正确生成所有可能的时间表。即：
- 0
- 0 1
- 0 1 2
- 0 1 2 3
- 0 1 2 3 4
- 0 1 2 4
- 0 1 2 4 3
- 0 1 3
- .....
- 1
- 1 0
- 1 0 2
- .....
优化
现在，上面的基本方法有一些低效之处。例如，当您正在构建可能的时间表时，您构建了一个由于截止日期标准而无法实现的时间表。例如：
- 3 5
是一个不可能的时间表，因为游戏“5”的截止日期为 1（这意味着它只能作为第一场比赛进行，或者不能全部进行）。如果你能认识到这一点，那么你就会意识到任何以3 5（3 5 0 ...、3 5 1 ...）开头的时间表也是不可能的。
如果您以巧妙的顺序生成计划并跳过您知道不可能的计划的生成，则可以利用这一事实。
算法提示
我建议以递归方式生成时间表。您的所有游戏 ID（0、1 等）都在 collection 中。您从最低索引开始：0，将其从游戏 collection 中删除 并将其放入暂定时间表：
日程安排：0
你检查它是否是一个有效的时间表（即你刚放在你的时间表中的游戏当时是否可以玩）。让我们假设是这种情况（在这种特定情况下，因为它是时间表上的第一场比赛，所以它应该总是可能的）。您还可以检查这个暂定时间表是否比您目前找到的任何时间表产生更好的分数。
然后您尝试添加 collection 剩余游戏中剩余的最低游戏。在这种情况下，1。同样，您从 collection 场比赛中删除 1 并将其列入您的日程安排：
日程安排：0 1
同样的事情，你检查这是否是一个有效的时间表。您已经知道游戏 0 可以先玩，您检查游戏 1 是否可以在第二个位置玩。运气不好，游戏的时间限制1让你无法做到。不再值得探索以 0 1 开头的时间表。您将 1 从您的日程安排中删除，但您不会在比赛中替换它 collection：因为不可能排在第二位，因此不值得进一步检查。相反，我会把它放在 collection 个在当前探索级别被“排除”的游戏中。
然后您继续进行游戏 collection、2 中剩余的下一场游戏并遵循相同的程序。如果您能够将与时间限制兼容的游戏安排在您的日程安排中，您可以继续将游戏添加到您的日程安排中，并保留在游戏 collection 中。请注意，可能存在您完全排满日程但仍有比赛剩余的情况（反之亦然，您的日程安排仍有漏洞但没有比赛可以剩余）。
当您 运行 没有选择时，是时候从日程表中删除游戏了。删除您安排在日程表上的最后一场比赛并将其放回比赛 collection。还将您在当前级别排除的游戏放回游戏 collection 中。您可以继续生成计划。不过，请注意不要再次使用您刚刚在此级别删除的游戏。