IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

 
 Ответить  Открыть новую тему 
> help! равномерное распределение работ
сообщение
Сообщение #1





Группа: Пользователи
Сообщений: 3

Репутация: -  0  +


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

помогите написать прогу. или хотя бы алгоритм. а то меня застопорило..
писать можно но паскали или с++.
буду очень признательна.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Новичок
*

Группа: Пользователи
Сообщений: 26

Репутация: -  0  +


чтото при прочтении задачи мне вспоминается университетский курс комбинаторики, почему не знаю. Наверно это одна из тех задач, которую надо сначала решить на бумаге а потом писать прогу.
ЗЫ: А что значит распределить более или менее? наверно все же найти минимальную напряженность месяца, так? а задача полностью сформулирована?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Новичок
*

Группа: Пользователи
Сообщений: 29

Репутация: -  0  +


и срок к которому надо скажиsmile.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Гость






срок к 16.10.

(не collapse, но знаю. smile.gif )
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5





Группа: Пользователи
Сообщений: 3

Репутация: -  0  +


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

предмет - комбинаторные алгоритмы=)
сдать надо к четвергу, т.е. 16 окт.
буду признательна за помощь=)
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Четыре квадратика
****

Группа: Пользователи
Сообщений: 579
Пол: Мужской

Репутация: -  4  +


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

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.

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


--------------------
Закон добровольного труда Зимерги:
Люди всегда согласны сделать работу, когда необходимость в этом уже отпала
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7





Группа: Пользователи
Сообщений: 3

Репутация: -  0  +


пасип=)
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


Бывалый
***

Группа: Пользователи
Сообщений: 195
Пол: Женский

Репутация: -  0  +


;D


--------------------
непонимающая..
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9


Четыре квадратика
****

Группа: Пользователи
Сообщений: 579
Пол: Мужской

Репутация: -  4  +


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

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

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


--------------------
Закон добровольного труда Зимерги:
Люди всегда согласны сделать работу, когда необходимость в этом уже отпала
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 22.09.2020 16:11
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name