![]() |
1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code].
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!
![]() ![]() |
![]() |
collapse |
![]()
Сообщение
#1
|
![]() Группа: Пользователи Сообщений: 3 Репутация: ![]() ![]() ![]() |
задача: есть предприятие. m видов работ, n месяцев. работы неделимы. трудоёмкости у каждой работы соотв-но b[i]. надо более или менее равномерно распределить работы по месяцам так, чтобы максимальная напряженность месяца была минимальной из всех возможных, т.е. max (суммаb[i]) ->min
(сумма b[i] - напряженность какого-то месяца) n>6; m>20 помогите написать прогу. или хотя бы алгоритм. а то меня застопорило.. писать можно но паскали или с++. буду очень признательна. |
Camel_Toe |
![]()
Сообщение
#2
|
![]() Новичок ![]() Группа: Пользователи Сообщений: 26 Репутация: ![]() ![]() ![]() |
чтото при прочтении задачи мне вспоминается университетский курс комбинаторики, почему не знаю. Наверно это одна из тех задач, которую надо сначала решить на бумаге а потом писать прогу.
ЗЫ: А что значит распределить более или менее? наверно все же найти минимальную напряженность месяца, так? а задача полностью сформулирована? |
orko |
![]()
Сообщение
#3
|
![]() Новичок ![]() Группа: Пользователи Сообщений: 29 Репутация: ![]() ![]() ![]() |
и срок к которому надо скажи
![]() |
... |
![]()
Сообщение
#4
|
Гость ![]() |
срок к 16.10.
(не collapse, но знаю. ![]() |
collapse |
![]()
Сообщение
#5
|
![]() Группа: Пользователи Сообщений: 3 Репутация: ![]() ![]() ![]() |
точная формулировка: в течение n месяцев предприятию необх-мо выполнить m работ, заданы b[i] - трудоёмкости. каждая работа может выполняться в течение только одного месяца (неважно, которого). требуется составить наиболее равномерный план работы предприятия, разбив перечень работ на группы по месяцам так, чтобы планируемый объем работ в течение наиболее напряженного месяца был минимальным.
размерность: n>=6, m>=20 предмет - комбинаторные алгоритмы=) сдать надо к четвергу, т.е. 16 окт. буду признательна за помощь=) |
trminator |
![]()
Сообщение
#6
|
Четыре квадратика ![]() ![]() ![]() ![]() Группа: Пользователи Сообщений: 579 Пол: Мужской Репутация: ![]() ![]() ![]() |
Посылаю еще раз, вчера были глюки, не прислалось
Код 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 |
![]()
Сообщение
#7
|
![]() Группа: Пользователи Сообщений: 3 Репутация: ![]() ![]() ![]() |
пасип=)
|
fms |
![]()
Сообщение
#8
|
![]() Бывалый ![]() ![]() ![]() Группа: Пользователи Сообщений: 195 Пол: Женский Репутация: ![]() ![]() ![]() |
;D
-------------------- непонимающая..
|
trminator |
![]()
Сообщение
#9
|
Четыре квадратика ![]() ![]() ![]() ![]() Группа: Пользователи Сообщений: 579 Пол: Мужской Репутация: ![]() ![]() ![]() |
Эта прога не работает. Решение должно быть кардинально другим.
Тест: 2 дня, работы: 5 5 3 3 3 Программа выдаст 8 и 11, правильный ответ - 10 и 9. Возможные пути решения: - Полный перебор ![]() - Можно оценить продолжительность работ для каждого дня сверху как сумму продолжительностей всех работ, снизу - как сумму продолжительностей всех работ, деленную на количество дней. Это позволит снизить перебор (наверно) ЗЫ препод этого не заметил... я был о нем лучшего мнения -------------------- Закон добровольного труда Зимерги:
Люди всегда согласны сделать работу, когда необходимость в этом уже отпала |
![]() ![]() |
![]() |
Текстовая версия | 25.07.2025 23:32 |