使用 C 的加权非重叠作业调度
Weighted non overlapping job scheduling using C
我已经使用了这个用 C++ 编写的示例
http://www.geeksforgeeks.org/weighted-job-scheduling-log-n-time/
这是 C 实现
#include <stdio.h>
#include <stdlib.h>
#define max(a,b) \
({ __typeof__ (a) _a = (a); \
__typeof__ (b) _b = (b); \
_a > _b ? _a : _b; })
//#ifndef max
// #define max(a,b) ((a) > (b) ? (a) : (b))
//#endif
struct rent
{
int starttime, endtime, profit;
};
int sort_event(const void * st1, const void * st2)
{
struct rent s1, s2;
s1.endtime = *(int*)st1;
s2.endtime = *(int*)st2;
return (s1.endtime < s2.endtime);
}
int binarySearch(struct rent rents[], int index)
{
// Initialize 'lo' and 'hi' for Binary Search
int lo = 0, hi = index - 1;
// Perform binary Search iteratively
while (lo <= hi)
{
int mid = (lo + hi) / 2;
if (rents[mid].endtime <= rents[index].starttime)
{
if (rents[mid + 1].endtime <= rents[index].starttime)
lo = mid + 1;
else
return mid;
}
else
hi = mid - 1;
}
return -1;
}
int findMaxProfit(struct rent arr[], int n)
{
qsort(arr, sizeof(arr+n), sizeof(int), sort_event);
int *table = (int *) malloc(sizeof(n));
table[0] = arr[0].profit;
// Fill entries in table[] using recursive property
for (int i=1; i<n; i++)
{
// Find profit including the current job
int inclProf = arr[i].profit;
int l = binarySearch(arr, i);
if (l != -1)
inclProf += table[l];
// Store maximum of including and excluding
table[i] = max(inclProf, table[i-1]);
}
// Store result and free dynamic memory allocated for table[]
int result = table[n-1];
free(table);
return result;
}
int main()
{
struct rent arr1[] = {{3, 10, 20}, {1, 2, 50}, {6, 19, 100}, {2, 100, 200}};
int n = sizeof(arr1)/sizeof(arr1[0]);
printf("\nOptimal profit is %d\n", findMaxProfit(arr1, n));
return 0;
}
预期的结果是250。经过进一步调查,我发现C中的qsort()有不同的实现。 sort() 即 incsort。但是我不确定这是唯一的原因还是什么。任何人都可以建议哪里可能是失礼。
在我看来,您似乎错误地调用了 qsort
。
试试这个:
qsort(arr, n, sizeof(struct rent), sort_event);
^^^ ^^^^
Number of elements Element size
"Functors" 在 C 和 C++ 中的工作方式不同。如果 s1 小于、等于或大于 s2,qsort
和 bsearch
需要一个 return 值小于、等于或大于 0 的函数。
在 C++ 中,仿函数只会执行其中之一,例如 return 如果较小则为真,否则为假。
将代码更改为return s1.endtime - s2.endtime;
此外,您对qsort
的呼吁是胡说八道。正如另一个答案中指出的那样,您提供了错误的参数。 sizeof(arr+n)
应该只是 n
。 qsort
想要项目数,而不是字节数。而且你使用 sizeof
不正确 - 你甚至不能在像 arr
这样的函数参数上使用它。
我已经使用了这个用 C++ 编写的示例 http://www.geeksforgeeks.org/weighted-job-scheduling-log-n-time/
这是 C 实现
#include <stdio.h>
#include <stdlib.h>
#define max(a,b) \
({ __typeof__ (a) _a = (a); \
__typeof__ (b) _b = (b); \
_a > _b ? _a : _b; })
//#ifndef max
// #define max(a,b) ((a) > (b) ? (a) : (b))
//#endif
struct rent
{
int starttime, endtime, profit;
};
int sort_event(const void * st1, const void * st2)
{
struct rent s1, s2;
s1.endtime = *(int*)st1;
s2.endtime = *(int*)st2;
return (s1.endtime < s2.endtime);
}
int binarySearch(struct rent rents[], int index)
{
// Initialize 'lo' and 'hi' for Binary Search
int lo = 0, hi = index - 1;
// Perform binary Search iteratively
while (lo <= hi)
{
int mid = (lo + hi) / 2;
if (rents[mid].endtime <= rents[index].starttime)
{
if (rents[mid + 1].endtime <= rents[index].starttime)
lo = mid + 1;
else
return mid;
}
else
hi = mid - 1;
}
return -1;
}
int findMaxProfit(struct rent arr[], int n)
{
qsort(arr, sizeof(arr+n), sizeof(int), sort_event);
int *table = (int *) malloc(sizeof(n));
table[0] = arr[0].profit;
// Fill entries in table[] using recursive property
for (int i=1; i<n; i++)
{
// Find profit including the current job
int inclProf = arr[i].profit;
int l = binarySearch(arr, i);
if (l != -1)
inclProf += table[l];
// Store maximum of including and excluding
table[i] = max(inclProf, table[i-1]);
}
// Store result and free dynamic memory allocated for table[]
int result = table[n-1];
free(table);
return result;
}
int main()
{
struct rent arr1[] = {{3, 10, 20}, {1, 2, 50}, {6, 19, 100}, {2, 100, 200}};
int n = sizeof(arr1)/sizeof(arr1[0]);
printf("\nOptimal profit is %d\n", findMaxProfit(arr1, n));
return 0;
}
预期的结果是250。经过进一步调查,我发现C中的qsort()有不同的实现。 sort() 即 incsort。但是我不确定这是唯一的原因还是什么。任何人都可以建议哪里可能是失礼。
在我看来,您似乎错误地调用了 qsort
。
试试这个:
qsort(arr, n, sizeof(struct rent), sort_event);
^^^ ^^^^
Number of elements Element size
"Functors" 在 C 和 C++ 中的工作方式不同。如果 s1 小于、等于或大于 s2,qsort
和 bsearch
需要一个 return 值小于、等于或大于 0 的函数。
在 C++ 中,仿函数只会执行其中之一,例如 return 如果较小则为真,否则为假。
将代码更改为return s1.endtime - s2.endtime;
此外,您对qsort
的呼吁是胡说八道。正如另一个答案中指出的那样,您提供了错误的参数。 sizeof(arr+n)
应该只是 n
。 qsort
想要项目数,而不是字节数。而且你使用 sizeof
不正确 - 你甚至不能在像 arr
这样的函数参数上使用它。