下一个→ ←上一页

c++中的活动选择问题

活动选择是计算机科学中的一个经典问题，可以用贪心算法来解决。在这个问题中，我们得到了一组将在给定时间段内执行的活动，每个活动都有开始时间和结束时间。目标是选择可以执行的活动的最大数量，这样就不会有两个活动重叠。

让我们考虑一个例子来更好地理解这个问题。假设你有五个活动:A, B, C, D, E，每个活动的开始和结束时间如下:

A:开始= 1，结束= 4

B:开始= 3，结束= 5

C: start = 0, end = 6

D: start = 5, end = 7

E:开始= 8，结束= 9

我们可以看到，如果我们执行活动A和D，就会出现冲突，因为这两个活动重叠。因此，目标是选择可以在没有任何冲突的情况下执行的活动的最大数量。这个问题的解决方案可以使用贪心算法找到。贪婪算法背后的思想是总是选择先完成的下一个活动。这确保我们有最大的时间来完成下一个活动。

下面是我们如何在c++中实现活动选择问题:

c++代码

            #include <bits/stdc++.h> using namespace std;struct Activity {int start, end;};bool比较(活动a，活动b){返回(a.end < b.end);}无效printMaxActivities(活动arr[]， int n) {sort(arr, arr + n，比较);cout << "下列活动已选定:\n";Int I = 0;Cout << "(" << arr[i]。开始<< "，" << arr[i]。End << ")， ";For (int j = 1; j < n; j++) { if (arr[j].start >= arr[i].end) { cout << "(" << arr[j].start << ", " << arr[j].end << "), "; i = j; } } } int main() { Activity arr[] = {{5, 9}, {1, 2}, {3, 4}, {0, 6}, {5, 7}, {8, 9}}; int n = sizeof(arr) / sizeof(arr[0]); printMaxActivities(arr, n); return 0; }
           

在上面的代码中，我们首先根据活动的结束时间对活动进行排序，因为我们希望选择最先结束的活动。然后，我们使用两个指针i和j来跟踪当前活动和下一个活动。我们从i = 0和j = 1开始，并将下一个活动的开始时间与当前活动的结束时间进行比较。如果下一个活动的开始时间大于或等于当前活动的结束时间，我们可以在没有任何冲突的情况下执行两个活动，因此我们增加j并设置i = j。这一直持续到j到达数组的末尾。该算法的时间复杂度为O(nlogn)，因为我们需要先对活动进行排序，这需要O(nlogn)时间。该算法的空间复杂度为0(1)，因为我们没有使用任何额外的空间。

输出

选择以下活动:(1,2)，(3,4)，(5,7)，(8,9)，

解释:

以上代码在c++中使用贪心算法实现了活动选择问题。活动选择问题是计算机科学中的一个经典问题，在该问题中，我们给定一组在给定时间段内要执行的活动，并且每个活动都有开始时间和结束时间。目标是选择可以在没有任何冲突的情况下执行的活动的最大数量，这样就不会有两个活动重叠。

代码从包含bits/stdc++.h头文件开始，该文件包含所有标准c++库。然后，定义Activity结构来存储每个活动的开始和结束时间。接下来，定义比较函数，该函数用于根据活动的结束时间对其进行排序。我们基于结束时间对活动进行排序的原因是我们希望选择先完成的活动。这确保我们有最大的时间来完成下一个活动。

printMaxActivities函数接受一个活动数组及其大小作为参数，并实现贪婪算法来解决活动选择问题。该函数首先使用排序函数和比较函数根据活动的结束时间对其进行排序。

下一个话题活动选择程序在c++

←上一页下一个→