Взвешенное неперекрывающееся планирование заданий с использованием 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. После дальнейшего изучения я обнаружил, что qsort() в C имеет другую реализацию по сравнению с. sort() который является incsort. Однако я не уверен, является ли это единственной причиной или чем. Может ли кто-нибудь, пожалуйста, предложить, где может быть подделка.

Источник

2 ответа

Решение

"Функторы" в C и C++ работают по-разному. qsort а также bsearch ожидает функцию, которая возвращает значение меньше, равно или больше 0, если s1 меньше, равно или больше s2.

В C++ функтор будет выполнять только одно из них, например, вернуть true, если меньше, иначе false.

Измените код на return s1.endtime - s2.endtime;

Кроме того, ваш звонок qsort ерунда Как указано в другом ответе, вы даете неправильные параметры. sizeof(arr+n) должно быть просто n, qsort хочет количество элементов, а не количество байтов. И вы используете sizeof неправильно - вы даже не можете использовать его в параметре функции, например arr является.

Источник

Мне кажется, что вы звоните qsort неправильно.

Попробуйте это вместо этого:

qsort(arr,     n,            sizeof(struct rent), sort_event);
              ^^^                ^^^^
  Number of elements          Element size
Источник
Другие вопросы по тегам