Задача о назначениях

[pinmix]

Помогите пожалуйста написать программу на С, а точнее дваже 2...

Задача такая:

Задача о назначениях.

Имеется n работников и n работ. Стоимость назначения i-того работнтника на j-тую работу равна Cij.

Задача состоит в отыскании назначения, при котором каждая работа выполняется некоторым человеком и которое имеет минимальную стоимость.

Нужно реализовать 2 алгоритма задачи о назначениях.

1) Жадный алгоритм

2) Метод ветвей и границ

Тем кто поможет - заранее спасибо!

Благодарности не будет границ! :)

[Delphi]

Как я понял есть матрица n*n в которой каждый столбец это работник, а каждая строка это работа- это пример, и получаеться надо найти на каку работу будет затрачено меньше денег правильно я понял??

если дя то вопрос такой может ли один работник выполнять боьше одной работы?

[pinmix]

Delphi: Матрица - это метод ветвей и нраниц (именно так организовывается запись и хранение информации в этом методе), аточнее не матрица а двумерный массив! :)

А суть ты понял верно!

И естественно один работник может выполнять больше одной работы но не одновременно, а занчит смысла большого в этом при данных условиях в этом нет, но алгортм допускает такой вариант, и лучше что бы к-во работниуов было n, а к-во работ - m, мало ли - ошибка в постановке задачи..

А вот как реализовывается жадный алгоритм в Си - я абсолютно без понятия))

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

А вообще алгоритмы простые, из учебников, могу даже лит-ру подсказать по этому поводу:

"Комбинаторные Алгоритмы", Рейнгольд

"Введение в прикладную комбинаторику", Коффман

Просто щас загруз очень большой, много чего еще надо сделать...

[skeletor]

Если напишешь на Паскале или Алгоритмическом языке - переведу на С.

[Delphi]

как ч понял надо реализовать эти два алгоритма к задачи

на каком языке реализовывать?

skeletor подпись у тебя просто бомба

[pinmix]

Delphi:

1) уху

2) на С (Си)

[Delphi]

Delphi:

1) уху

2) на С (Си)

сейчас поищю алгоритмы на с может быть проблема давно неписал на нем