Форум на Исходниках.RU

Задача

Igrek — Mon, 05 Sep 2011 05:44:34 +0000

Igrek: Swetlana, большое спасибо!

Задача

Swetlana — Fri, 02 Sep 2011 17:19:11 +0000

Swetlana: Вот исходники на си
distr.rar (, : 109)

Добавлено 02.09.11, 17:44
Да, забыла сказать. У вас все контейнеры имеют одинаковую вместимость. а там вместимость каждого контейнера либо генерится сл. образом, либо задаётся. Наверно, в текстовом файле.

Задача

Swetlana — Fri, 02 Sep 2011 17:14:44 +0000

Swetlana: Вот исполняемый файл, с его константами
Project1.rar (, : 118)

Задача

Swetlana — Fri, 02 Sep 2011 17:13:52 +0000

Swetlana: Igrek, почитайте... Вообще-то там ваша задача решена :)
Дипломник-заочник эту задачу делал, начал за 3 недели до защиты, ночью перед защитой презентацию доделал. Ответственности я за его программу (на си) не несу, на защите вроде работала.
Открываете файл unit1.cpp, видите

Цитата

double P = 0.8; // процент заполненности
int NNC=5; // количество контейнеров для рандома
int NNT=15; // количество предметов для рандома

Для вашей задачи 0,8 маловато, поставьте 0,9. Ну, и если хотите на случайных данных погонять, установите 3 контейнера (3 фазы) и своё количество автоматов (предметов). Данные, насколько мне помнится читаются из файла, в текстовом файле задаёте количество контейнеров, предметов, их размеры.
Вот презентация
___________.rar (, : 272)

Задача

Igrek — Fri, 02 Sep 2011 13:50:27 +0000

Igrek: Swetlana, спасибо, почитаю....

Задача

Swetlana — Fri, 02 Sep 2011 11:36:58 +0000

Swetlana: Igrek, так бы сразу и сказали, что задача производственная, а вы - не студент-двоешник.
Если размерность маленькая, n<= 25, можно решить перебором, методом ветвей и границ.

Для большой размерности такие задачи очень хорошо решаются локальным поиском. Я решала неоднократно. :)
Разобранный пример с программой на паскале можно найти здесь, работы равномерно по бригадам распределяются.
http://www.mesforum.ru/viewtopic.php?f=6&t=1569

Задача

Akina — Fri, 02 Sep 2011 08:09:29 +0000

Akina:

Цитата Igrek @ 02.09.11, 08:06

По сути, так и действует человек...

Нет, как раз чел дейтсвует так, как ты пробовал - наполняет рюкзаки по одному.

Задача

Igrek — Fri, 02 Sep 2011 08:06:54 +0000

Igrek: Akina, попробую. По сути, так и действует человек...

Задача

Akina — Fri, 02 Sep 2011 07:58:51 +0000

Akina:

Цитата Igrek @ 02.09.11, 06:21

Сейчас пробую реализовать жадный алгоритм (когда "рюкзаки" по очереди забиваем максимальными возможными элементами).

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

Задача

Igrek — Fri, 02 Sep 2011 07:53:48 +0000

Igrek: Алгоритм очень не оптимальный в некоторых случаях...

Задача

Igrek — Fri, 02 Sep 2011 06:21:44 +0000

Igrek: Swetlana, это производственная задача, область электрика. Необходим алгоритм для балансировки фаз. Есть три фазы и n автоматов, необходимо их раскидать по фазам, чтоб сила тока автоматом была более менее сбалансирована.
Важна производительность, а не оптимальность решения, достаточно решения удовлетворяющего условиям.

Сейчас пробую реализовать жадный алгоритм (когда "рюкзаки" по очереди забиваем максимальными возможными элементами).

Пример.

25 15 13 10 8 7 5 3 1 1 1 (уже отсортирован)

ограничение будет, если округлить до минимальной погрешности <=30

Решение.
Первый 25 + 3 + 1 + 1 = 30 (на каждом шаге берем максимально допустимы элемент)
Второй 15 + 13 + 1 = 29
Третий 10 + 8 + 7 + 5 = 30

Задача

Swetlana — Thu, 01 Sep 2011 17:44:31 +0000

Swetlana: Не могу понять, есть ли полиномиальная сводимость 3-Разбиения к данной задаче.

3-РАЗБИЕНИЕ.
Условие. Заданы множество A, состоящее из 3m элементов, целое положительное число B. Элементы имеют целые положительные размеры такие, что
1. B/4 < s(a) < B/2
2. Сумма размеров всех элементов равна mB.
Вопрос. Можно ли множество A разбить на m непересекающихся подмножеств так, что сумма элементов каждого i-го подмножества равна В? (и каждое подмножество содержит ровно 3 элемента).
Похоже ограничения на размеры и количества даны так, чтобы исключить тривиальные случаи.

Вообще, одно дело точно набирать сумму, другое дело - примерно. Примерно это как? Минимизируем среднеквадратичное отклонение по всем кучкам? Или максимальное отклонение должно быть минимально?

Добавлено 01.09.11, 17:51
Igrek, это учебная задача или производственная?
Для небольшой размерности она решается переборными алгоритмами, например, как предложил MBo.

Задача

Swetlana — Thu, 01 Sep 2011 15:50:18 +0000

Swetlana: Akina,
вот как раз этим занимаюсь :) раскладыванием слагаемых по кучкам, число кучек больше либо равно три,
класс задачи уточняю. Но это к слову.

Один рюкзак здесь не подойдёт, тут 3 рюкзака. И вообще здесь ближе не рюкзак,
3-РАЗБИЕНИЕ, NP-трудная в сильном смысле, т.е. за псевдополиномиальное время ДП её не решить. А рюкзак ДП решается куда как хорошо.
Алгоритм который Mbo привёл - метод ветвей и границ, что для NP-трудной в сильном смысле естесственно.
А рюкзачок - задача динамического программирования.

Задача

Akina — Thu, 01 Sep 2011 14:40:40 +0000

Akina:

Цитата Igrek @ 01.09.11, 13:56

Классические задачи этого типа имеют два параметра типа "вес" и "ценность", здесь только один....

вес = const

Задача

MBo — Thu, 01 Sep 2011 14:22:02 +0000

MBo: http://kladovka.net.ru/delphibase/?action=viewfunc&topic=mathalg&id=10413

Задача

Igrek — Thu, 01 Sep 2011 13:56:28 +0000

Igrek: Классические задачи этого типа имеют два параметра типа "вес" и "ценность", здесь только один....
Какие существуют алгоритмы для данной задачи?

Задача

Igrek — Wed, 31 Aug 2011 11:50:18 +0000

Igrek: Спасибо.

Задача

Akina — Wed, 31 Aug 2011 11:40:40 +0000

Akina: Замешай все числа в кучу, после чего решай стандартную задачу распределения грузов по вагонам (ну или задача о ранце).

Задача

Igrek — Wed, 31 Aug 2011 11:32:32 +0000

Igrek: Есть следующая задача (я не знаю, как называется тип этих задач). Имеется n наборов чисел, необходимо перераспределить числа в этих наборах так, чтобы сумма чисел в каждом наборе была равна или примерна равна.

Пример. Есть три набора:
3, 5, 1;
10, 1, 4;
12, 3, 2, 1.
Общая сумма всех чисел равна 42, соответственно в каждом наборе должно быть 42/3=14.
Одно из решений следующее: из третьей в первую переносим числа 3 и 2, из второй в третью переносим число 1.
Получаем
3, 5, 1, 3, 2
10, 4
12, 1, 1

Насколько понимаю, эта задача типовая задача, но я не знаю как называется такая задача, поэтому в поиске найти ни чего не смог.
Подскажите возможные алгоритмы решения данной задачи.