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

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

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

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





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

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


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

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


Новичок
*

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

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


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


Новичок
*

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

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


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


Гость






срок к 16.10.

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





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

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


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

предмет - комбинаторные алгоритмы=)
сдать надо к четвергу, т.е. 16 окт.
буду признательна за помощь=)
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
trminator
сообщение 11.10.2003 14:27
Сообщение #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 
 К началу страницы 
+ Ответить 
collapse
сообщение 11.10.2003 15:00
Сообщение #7





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

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


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


Бывалый
***

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

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


;D


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


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

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

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


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

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

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


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

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

 

- Текстовая версия 25.07.2025 23:32
Хостинг предоставлен компанией "Веб Сервис Центр" при поддержке компании "ДокЛаб"