Составить наиболее равномерный план работы предприятия, разбив перечень работ на группы по месяцам - C (СИ)

Формулировка задачи:

Доброго времени суток. Вот застала врасплох одна задачка, у которой не существует оптимального алгоритма решения (она так же известна как задача о камнях). Но проблема не в этом =) Формулировка: В течение n месяцев предприятию необходимо выполнить m работ, заданы b[i]>0 - их трудоемкости, целые числа (от 1 до m). Каждая работа может выполняться в течение только одного месяца (неважно, которого). Требуется составить наиболее равномерный план работы предприятия, разбив перечень работ на группы по месяцам так, чтобы планируемый объем работ в течение наиболее напряженного месяца был минимальным. Помогите разобраться, как создать N массивов по числу n-месяцев? Эвристический алгоритм для задачи: На каждом шаге брать самую тяжёлую работу из оставшихся и записывать её в самый лёгкий месяц Кусок того, что я начал писать если что =)

#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#define MAX_SIZE 255
 
int main (){
    int n;                  // число месяцев
    int m;                  // число работ
    int b[MAX_SIZE];        // массив с трудоёмкостями
    int i,j;                // счётчики
    int str[MAX_SIZE];
    FILE *Fpin;
    FILE *Fpout;

    Fpin=fopen("input.txt","r");
    Fpout=fopen("output.txt","w");
 
/* Сканирование данных из файла */
    fscanf(Fpin,"%d",&m);
    fscanf(Fpin,"%d",&n);
    for(i=0;i<m;i++)
    {
        fscanf(Fpin,"%d",str);
        b[i]=str[0];
    }

/* Просто проверка правельности записи в массиве */
    for(i=0;i<m;i++)
        fprintf(Fpout,"%d ",b[i]);
    fprintf(Fpout,"\n");
    fprintf(Fpout,"m=%d ",m);
    fprintf(Fpout,"\n");
    fprintf(Fpout,"n=%d ",n);

    fclose(Fpin);
    fclose(Fpout);
    return 0;
}

Решение задачи: «Составить наиболее равномерный план работы предприятия, разбив перечень работ на группы по месяцам»

Листинг программы

#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <math.h>
 
#define MONTH 30  // количество дней в месяц
#define MAX_SIZE 255
 
 
void insertSort(int a[], int size) {
    int x;
    long i, j;
 
    for ( i=0; i < size; i++) {  // цикл проходов, i - номер прохода
        x = a[i];   
        // поиск места элемента в готовой последовательности 
        for ( j=i-1; j>=0 && a[j] > x; j--)
            a[j+1] = a[j];    // сдвигаем элемент направо, пока не дошли
        // место найдено, вставить элемент
        a[j+1] = x;
    }
}
 
int main (){
    int numbMonth;             // число месяцев
    int numbWork;              // число работ
    int i,j, k, count;                       // счётчики
    int weigh=0;                             // весовой коэффициент=среднее количество рабочих дней в месяц 
    int delta, summ;
    FILE *Fpin;
    FILE *Fpout;
 
    Fpin=fopen("input.txt","r");
    Fpout=fopen("output.txt","w");
 
    /* Сканирование данных из файла */
    fscanf(Fpin,"%d",&numbWork);
    int *b=(int *)calloc(numbWork, sizeof(int));        // массив с трудоёмкостями
    int *workDay=(int *)calloc(numbWork, sizeof(int));        // массив с трудоднями
    int **pWork=(int **)calloc(numbWork, sizeof(int));        // массив указателей
    fscanf(Fpin,"%d",&numbMonth);
    for(i=0;i<numbWork;i++)
    {
        fscanf(Fpin,"%d",&b[i]);
        weigh+=b[i];
    }
 
    insertSort(b, numbWork);                    // сортируем массив 
                                                                        // взято с топика "Алгоритмы сортировки строк"
 
    // вычисление весового коэффициента с правильным округлением
    weigh=(weigh*10)/numbMonth;
    ((weigh%10)>=5)?weigh=weigh/10+1:weigh/=10;
 
    // !!! нет проверки количество месяцев - если один, посмеяться и расслабиться
    // !!! нет проверки на превышение весового коэффициента количества дней в месяце
 
    // рассовываем крупные работы превышающие весовой коэффициент (в конец массива)
    count=numbMonth;
    for(i=0;i<numbWork;i++)
    {
        if(b[i]>=weigh)
        { workDay[--count]=b[i]; /* b[i]=-b[i];*/}
    }
 
    // остальные работы распихиваем по критерию:
    // сумма работ как можно ближе к весовому коэффициенту
 
    // тут самое интересное, количество работ в месяце может быть numbWork-1
    // вариант с одним месяцем должен быть исключён раньше
    // пределы numbWork не оговоренны и при решении в лоб нужно
    // перебрать все возможные суммы для numbWork>5 уже не просто, а если
    // numbWork=50. большинство сумм превысить и на много весовой коэффициент,
    // но эти варианты всё равно считать
    // логичное ограничение это сложить первые (самые малые работы) до значения weigh
    // тогда максимальное количество работ огранничется weigh, 
    // а максимальное значение weigh = MONTH (30)
    // можно уменьшить до 29, но это не спасёт "отца российской демократии"
    // количество вариантов перебора для N слагаемых  =
    // = N+[сумма по x=1..N-1]((N-x)*(N-x-1)/2) - можно преобразовать ещё
 
    fclose(Fpin);
    fclose(Fpout);
    return 0;
}

Объяснение кода листинга программы

Код представляет собой функцию, которая сортирует массив работ по их трудоёмкости и распределяет их по месяцам с целью сделать нагрузку на предприятие наиболее равномерной. Список действий:

Заголовочные файлы и подключаемые библиотеки
Объявление переменных
Открытие файлов для чтения и записи
Чтение данных из файла: число работ и количество месяцев
Распределение памяти для массивов
Сортировка массива работ по трудоёмкости с использованием алгоритма сортировки пузырьком
Вычисление весового коэффициента (среднего количества рабочих дней в месяц)
Распределение крупных работ, превышающих весовой коэффициент, в конец массива
Распределение остальных работ по месяцам с учетом суммы работ, как можно ближе к весовому коэффициенту
Закрытие файлов
Возврат 0, что означает успешное выполнение программы Основная сложность возникает при распределении работ по месяцам, так как необходимо учесть, что количество работ в месяце может быть меньше общего количества работ. Весовой коэффициент вычисляется как среднее количество рабочих дней в месяц, и его значение может быть ограничено количеством дней в самом длинном месяце (например, 30 дней в месяце). Однако это ограничение не спасает от перебора всех возможных комбинаций распределения работ. При большом количестве работ (например, 50) большинство сумм превышают весовой коэффициент на много, но эти варианты все равно должны быть учтены. Код не содержит проверки на количество месяцев и не проверяет, не превысит ли весовой коэффициент количество дней в месяце. Также не оговорены пределы для количества работ.