help! равномерное распределение работ Опции

[collapse]

задача: есть предприятие. m видов работ, n месяцев. работы неделимы. трудоёмкости у каждой работы соотв-но b[i]. надо более или менее равномерно распределить работы по месяцам так, чтобы максимальная напряженность месяца была минимальной из всех возможных, т.е. max (суммаb[i]) ->min
(сумма b[i] - напряженность какого-то месяца)
n>6; m>20

помогите написать прогу. или хотя бы алгоритм. а то меня застопорило..
писать можно но паскали или с++.
буду очень признательна.

[Camel_Toe]

чтото при прочтении задачи мне вспоминается университетский курс комбинаторики, почему не знаю. Наверно это одна из тех задач, которую надо сначала решить на бумаге а потом писать прогу.
ЗЫ: А что значит распределить более или менее? наверно все же найти минимальную напряженность месяца, так? а задача полностью сформулирована?

[orko]

и срок к которому надо скажи

[...]

срок к 16.10.

(не collapse, но знаю. )

[collapse]

точная формулировка: в течение n месяцев предприятию необх-мо выполнить m работ, заданы b[i] - трудоёмкости. каждая работа может выполняться в течение только одного месяца (неважно, которого). требуется составить наиболее равномерный план работы предприятия, разбив перечень работ на группы по месяцам так, чтобы планируемый объем работ в течение наиболее напряженного месяца был минимальным.
размерность: n>=6, m>=20

предмет - комбинаторные алгоритмы=)
сдать надо к четвергу, т.е. 16 окт.
буду признательна за помощь=)

[trminator]

Посылаю еще раз, вчера были глюки, не прислалось

Код

program workplan;
{$APPTYPE CONSOLE}
uses
 SysUtils;
const inf = 1000000; //infinity

type TVect = array[1..100] of Integer;
    TPlan = array[-1..100,1..100] of Integer;

var works   : TVect;
   plan    : TPlan;
   n, m, i : integer;  //n days, m works
   k,c, avail:integer;  //avail works left

function argmin: integer;
var i, min, nmin: integer;
begin min:=inf;
 for i:=1 to n do
   if plan[-1, i] < min then
     begin min:=plan[-1, i]; nmin:=i end;
 Result:=nmin;
end;

procedure swap(var a, b: integer);
var c: integer;
begin
 c:=a; a:=b; b:=c
end;

procedure sort(var a: TVect; n: integer);
var i, j: integer;
begin
 for i:=1 to n do
   for j:=n downto i do
     if a[i] > a[j] then swap(a[i], a[j]);
end;

procedure input;
var i: integer;
begin
  WriteLn('Input number of days > ');
  ReadLn(n);
  WriteLn('Input number of works > ');
  ReadLn(m);
  for i:=1 to m do
    begin
      Write('Input cost for work # ',i,' > ');
      ReadLn(works[i])
    end;
end;

procedure output;
var i, j: integer;
begin
 WriteLn('-------------------------');
 for i:=1 to n do
   begin
     for j:=1 to plan[0, i] do write(plan[j, i], ' ');
     writeLn('Total: ', plan[-1, i])
   end;
end;

begin
 input; avail:=m;
 sort(works, m);
 fillchar(plan, sizeof(plan), 0);
 for i:=1 to m do
   begin
      k:=argmin;
      c:=works[avail];
      inc(plan[-1, k],c);
      inc(plan[0, k]);
      plan[plan[0,k], k]:=c;
      dec(avail)
   end;
 output;
 Readln;
end.

ЗЫ Сдавалась в ПетрГУ, Комбинаторные алгоритмы, Касьянову, на этой неделе.
(просто есть подозрение, что эта прога пойдет туда же )

[collapse]

пасип=)

[fms]

;D

[trminator]

Эта прога не работает. Решение должно быть кардинально другим.
Тест: 2 дня, работы: 5 5 3 3 3
Программа выдаст 8 и 11, правильный ответ - 10 и 9.

Возможные пути решения:
 - Полный перебор
 - Можно оценить продолжительность работ для каждого дня сверху как сумму продолжительностей всех работ, снизу - как сумму продолжительностей всех работ, деленную на количество дней. Это позволит снизить перебор (наверно)

ЗЫ препод этого не заметил... я был о нем лучшего мнения