请详细解释该代码的含义:for (i = 0; i < n; i++) { for (j = jobs[i].deadline - 1; j >= 0; j--) { if (!selected[j]) { selected[j] = jobs[i].id; max_profit += jobs[i].profit; break; } } }
时间: 2024-02-15 16:27:15 浏览: 19
该代码实现了任务调度问题中的贪心算法,其含义如下:
1. 首先,外层循环 `for (i = 0; i < n; i++)` 遍历所有的任务。
2. 内层循环 `for (j = jobs[i].deadline - 1; j >= 0; j--)` 从任务的截止日期开始,向前遍历时间片。
3. 在内层循环中,如果当前时间片 `j` 没有被占用(即 `!selected[j]`),则将该时间片分配给当前任务,同时记录当前任务的利润 `max_profit`,并将 `selected[j]` 标记为已占用(即将 `selected[j]` 赋值为当前任务的 id),然后退出内层循环。
4. 如果当前时间片已被占用,则继续向前遍历时间片。
5. 最后,返回计算得到的总利润 `max_profit`。
该算法的核心思想是,优先安排利润高、截止期限紧的任务,以最大化总利润。在内层循环中,我们从截止日期开始,向前遍历时间片,找到第一个空闲的时间片,将当前任务安排在其中。这样做可以确保任务能在截止日期之前完成,并且能够最大化总利润。
相关问题
请逐行解释下面代码:#include <stdio.h> #include <stdlib.h> #define MAX_N 200 typedef struct job { int deadline; int profit; int id; } Job; int cmp(const void *a, const void *b) { return ((Job *)b)->profit - ((Job *)a)->profit; } int main() { int n, i, j, k, max_profit = 0; Job jobs[MAX_N]; int selected[MAX_N] = {0}; scanf("%d", &n); for (i = 0; i < n; i++) { scanf("%d%d", &jobs[i].deadline, &jobs[i].profit); jobs[i].id = i + 1; } qsort(jobs, n, sizeof(Job), cmp); for (i = 0; i < n; i++) { for (j = jobs[i].deadline - 1; j >= 0; j--) { if (!selected[j]) { selected[j] = jobs[i].id; max_profit += jobs[i].profit; break; } } } printf("%d\n", max_profit); for (i = 0; i < n; i++) { if (selected[i]) { printf("%d ", selected[i]); } } printf("\n"); return 0; }
这是一个求解任务调度问题的 C 语言程序,下面逐行解释:
```C
#include <stdio.h>
#include <stdlib.h>
#define MAX_N 200
typedef struct job {
int deadline; // 任务截止时间
int profit; // 任务收益
int id; // 任务编号
} Job;
```
这里导入了两个标准库头文件,定义了一个宏 MAX_N 和一个任务的结构体 Job,其中包含任务的截止时间、任务的收益和任务的编号。
```C
int cmp(const void *a, const void *b) {
return ((Job *)b)->profit - ((Job *)a)->profit;
}
```
这是排序函数 cmp,它是用来对任务数组 jobs 进行降序排序的,排序的依据是任务的收益。这里使用了标准库的快速排序函数 qsort,它需要传入待排序数组的首地址、数组元素个数、元素大小和排序函数。
```C
int main() {
int n, i, j, k, max_profit = 0;
Job jobs[MAX_N];
int selected[MAX_N] = {0};
scanf("%d", &n);
for (i = 0; i < n; i++) {
scanf("%d%d", &jobs[i].deadline, &jobs[i].profit);
jobs[i].id = i + 1;
}
qsort(jobs, n, sizeof(Job), cmp);
for (i = 0; i < n; i++) {
for (j = jobs[i].deadline - 1; j >= 0; j--) {
if (!selected[j]) {
selected[j] = jobs[i].id;
max_profit += jobs[i].profit;
break;
}
}
}
printf("%d\n", max_profit);
for (i = 0; i < n; i++) {
if (selected[i]) {
printf("%d ", selected[i]);
}
}
printf("\n");
return 0;
}
```
这是主函数,它首先定义了一些变量,包括任务个数 n、任务数组 jobs、已选择的任务 selected 和最大收益 max_profit,然后用 scanf 读入任务的截止时间和收益,并为每个任务赋予一个编号。接着使用 qsort 对任务数组 jobs 按照收益进行排序。
最后,程序使用贪心算法求解任务调度问题,首先遍历任务数组 jobs,对于每个任务,从它的截止时间开始往前遍历,如果当前时间点上还没有任务被选择,就将该任务选中,并将其收益加入最大收益中。最后输出最大收益和被选中的任务编号。
修改该代码,使其输出最后一个作业后面无空格:#include <stdio.h> #include <stdlib.h> #define MAX_N 200 typedef struct job { int deadline; int profit; int id; } Job; int cmp(const void *a, const void *b) { return ((Job *)b)->profit - ((Job *)a)->profit; } int main() { int n, i, j, k, max_profit = 0; Job jobs[MAX_N]; int selected[MAX_N] = {0};//已选的任务 scanf("%d", &n); for (i = 0; i < n; i++) { scanf("%d%d", &jobs[i].deadline, &jobs[i].profit); jobs[i].id = i + 1; } qsort(jobs, n, sizeof(Job), cmp);//将效益值从大到小排列 for (i = 0; i < n; i++) { for (j = jobs[i].deadline - 1; j >= 0; j--) { if (!selected[j]) { selected[j] = jobs[i].id; max_profit += jobs[i].profit; break; } } } printf("%d\n", max_profit); for (i = 0; i < n; i++) { if (selected[i]) { printf("%d ", selected[i]); } } printf("\n"); return 0; }
请将最后一个printf语句修改为如下代码,即可实现输出最后一个作业后面无空格:
```
for (i = 0; i < n; i++) {
if (selected[i]) {
printf("%d", selected[i]);
if (i != n-1) {
printf(" ");
}
}
}
printf("\n");
```
修改后的完整代码如下:
```
#include <stdio.h>
#include <stdlib.h>
#define MAX_N 200
typedef struct job {
int deadline;
int profit;
int id;
} Job;
int cmp(const void *a, const void *b) {
return ((Job *)b)->profit - ((Job *)a)->profit;
}
int main() {
int n, i, j, k, max_profit = 0;
Job jobs[MAX_N];
int selected[MAX_N] = {0};//已选的任务
scanf("%d", &n);
for (i = 0; i < n; i++) {
scanf("%d%d", &jobs[i].deadline, &jobs[i].profit);
jobs[i].id = i + 1;
}
qsort(jobs, n, sizeof(Job), cmp);//将效益值从大到小排列
for (i = 0; i < n; i++) {
for (j = jobs[i].deadline - 1; j >= 0; j--) {
if (!selected[j]) {
selected[j] = jobs[i].id;
max_profit += jobs[i].profit;
break;
}
}
}
printf("%d\n", max_profit);
for (i = 0; i < n; i++) {
if (selected[i]) {
printf("%d", selected[i]);
if (i != n-1) {
printf(" ");
}
}
}
printf("\n");
return 0;
}
```
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)