|
Помогите составить алгоритм.
|
||
|---|---|---|
Участник
Откуда: здесь была правда.<br /><br />Слоган: Делфи жив!!!
Сообщения: 30 377 |
||
| 24.09.2009, 14:32:29 |
|
|
|
|
|
Помогите составить алгоритм.
|
|||
|---|---|---|---|
|
#18+
Суть задачи такова: Есть таблица 5х50 12345№1124793№23615105№3361714..................№503426127 неоходимо вырать из каждого столбца по три значение, что бы их сумма(15 значений) была максимальна. Но... нельзя выбирать два значения из одной строки. Я надеюсь понятно описал. Помогите составить алгоритм расчета. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 24.09.2009, 13:42:01 |
|
||
|
Помогите составить алгоритм.
|
|||
|---|---|---|---|
|
#18+
Мы надеемся, что тебя отчислят. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 24.09.2009, 14:18:29 |
|
||
|
Помогите составить алгоритм.
|
|||
|---|---|---|---|
|
#18+
Сортируем 5 столбцов по убыванию. Затем сортируем столбцы по суммам 3-х максимальных чисел. Т.е. 24 21 12 9 2 9 8 5 4 1 8 7 4 3 1 7 6 3 2 0 затем берём 1,2,3 из 1-го, 4,5,6 из 2-го, и т.д. Это и будет максимальная сумма непересекаемых. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 24.09.2009, 14:22:57 |
|
||
|
Помогите составить алгоритм.
|
|||
|---|---|---|---|
|
#18+
AlexGruСортируем 5 столбцов по убыванию. Затем сортируем столбцы по суммам 3-х максимальных чисел. Т.е. 24 21 12 9 2 9 8 5 4 1 8 7 4 3 1 7 6 3 2 0 затем берём 1,2,3 из 1-го, 4,5,6 из 2-го, и т.д. Это и будет максимальная сумма непересекаемых.нет: 4,5 и 6-й второго столбца могут быть слишком маленькими ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 24.09.2009, 14:29:02 |
|
||
|
Помогите составить алгоритм.
|
|||
|---|---|---|---|
Участник
|
|||
|
#18+
Напоминает задачу о назначениях... Возможно, надо как-то модифицировать алгоритм для нее. Или попробовать прикрутить симплекс-метод... В общем, из этой категории что-то. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 24.09.2009, 14:32:29 |
|
||
|
Помогите составить алгоритм.
|
|||
|---|---|---|---|
|
#18+
второй столбец тоже отсортирован ведь по убыванию Naf[quot AlexGru]4,5 и 6-й второго столбца могут быть слишком маленькими все дело в сортировке. a1 b1 a2 b2 a3 b3 a4 b4 a5 b5 a6 b6 если a1>a1>a3... и b1>b2>b3.... и a1+a2+a3>b1+b2+b3, то берём вообще самую максим. тройку a1,a2,a3 тогда из столбца b нам запрещено брать b1,b2,b3 остается b4,b5,b6. Открываем биореактор. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 24.09.2009, 14:33:59 |
|
||
|
Помогите составить алгоритм.
|
|||
|---|---|---|---|
|
#18+
AlexGruвторой столбец тоже отсортирован ведь по убыванию если a1>a1>a3... и b1>b2>b3.... и a1+a2+a3>b1+b2+b3, то берём вообще самую максим. тройку a1,a2,a3 тогда из столбца b нам запрещено брать b1,b2,b3 остается b4,b5,b6. А как отсортироваль пять столбцов, не меняя их индексы? a1 b1 с1 a2 b2 с2 a3 b3 с3 a4 b4 с4 Допустим отсортировали столбец а, получили: a2 b2 с2 a3 b3 с3 a1 b1 с1 a4 b4 с4 т.е. а2>a3>a1>a4. Но стольбец b и с у нас не отсортированы!! ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 24.09.2009, 14:47:43 |
|
||
|
Помогите составить алгоритм.
|
|||
|---|---|---|---|
|
#18+
конечно можно перебором всех возможных значений, но это очень долго! Это получается 50!/(50-15)! итераций. как-то многовато. =) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 24.09.2009, 14:51:12 |
|
||
|
Помогите составить алгоритм.
|
|||
|---|---|---|---|
|
#18+
Cerber-88. Что значит не меняя их идексы. Это уже после сортировки. a1 b1 a2 b2 a3 b3 a4 b4 a5 b5 a6 b6 Если речь идёт о строках как о векторах, т.е при поднятии первого элемента по первому столбцу, мы должны двигать весь вектор, тогда это другая задача. Биореактор пока держим открытым. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 24.09.2009, 14:54:03 |
|
||
|
Помогите составить алгоритм.
|
|||
|---|---|---|---|
|
#18+
AlexGru Биореактор пока держим открытым. Вы меня видимо не правлино поняли. Речь как раз и идёт о строках как о векторах, т.е при поднятии первого элемента по первому столбцу, мы должны двигать весь вектор. Вот в этом то вся и загвоздка... ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 24.09.2009, 14:58:38 |
|
||
|
Помогите составить алгоритм.
|
|||
|---|---|---|---|
|
#18+
Яростный МечНапоминает задачу о назначениях... Возможно, надо как-то модифицировать алгоритм для нее. Или попробовать прикрутить симплекс-метод... В общем, из этой категории что-то. Именно так и есть. Симплекс-метод поможет, но в нем нет необходимости. Можно обойтись венгерским методом (см. тут например: http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=hungarianAlgorithm ). Единственное, что надо учесть -- это то, что каждый "рабочий" (столбец) может "выполнять" не одну, а сразу три "работы". Это делается элементарно -- каждому столбцу в соответствие ставится сразу три вершины левой доли графа ("рабочих"), с одинаковыми весами исходящих дуг. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 24.09.2009, 15:19:24 |
|
||
|
Помогите составить алгоритм.
|
|||
|---|---|---|---|
|
#18+
А нельзя так? Заводим 5 глоб переменных, счетчики для каждого из столбцов. 1) ищем 5 максим чисел по всей матрице.(чтобы не больше одного числа на вектор) считаем из этих 5-ти векторов, сколько максимумов приходится на соотв. столбец. например 1 2 1 2 1 Выбранные вектора исключаем из дальнейшего поиска. и так ещё столько раз пока. пока. не будет 3 3 3 3 3 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 24.09.2009, 15:40:41 |
|
||
|
|
start [/forum/topic.php?fid=16&fpage=117&tid=1344232]: |
0ms |
get settings: |
10ms |
get forum list: |
14ms |
check forum access: |
3ms |
check topic access: |
3ms |
track hit: |
67ms |
get topic data: |
9ms |
get forum data: |
2ms |
get page messages: |
45ms |
get tp. blocked users: |
1ms |
| others: | 213ms |
| total: | 367ms |
| 0 / 0 |
