Список форумов Шадринский форум -> Программирование -> Программирование для школьников и студентов. -> Задача о равномерном распределении чисел
Задача о равномерном распределении чисел
Автор
Сообщение
Шатунов
Заслуженный писатель
Пол:
Зарегистрирован: 16.07.2007
Сообщения: 2091
Откуда: Оренбургская обл.
Статус: Offline
Заслуженный писатель
Пол:
Зарегистрирован: 16.07.2007
Сообщения: 2091
Откуда: Оренбургская обл.
Статус: Offline
| Имеется массив А из N элементов ,где (1<=N<=10^6) (1<=A[i]<=10^3)
Задача: Разделить массив А на 2 массива B и С таким образом чтобы разница сумм элементов этих массивов была минимальна. Пример: Массив А 1 2 3 4 5 ------------------------------------ Массив В 5 2 1 Массив С 4 3 _________________ Даже когда тебя сожрали у тебя есть два выхода |
| Шатунов
один вариант допускается найти или все возможные? |
Шатунов
Заслуженный писатель
Пол:
Зарегистрирован: 16.07.2007
Сообщения: 2091
Откуда: Оренбургская обл.
Статус: Offline
Заслуженный писатель
Пол:
Зарегистрирован: 16.07.2007
Сообщения: 2091
Откуда: Оренбургская обл.
Статус: Offline
| clicks
Хотя бы один _________________ Даже когда тебя сожрали у тебя есть два выхода |
Шатунов писал(а): Хотя бы одинвот набросал на C, для примера http://codepad.org/yZH3rfa8 1. сортируем 1.2 находим сумму массива и делим на 2 2. к максимальному начинаем прибавлять минимальные 2.1.если сумма становится больше половины суммы массива а, останавливается. это получился массив b, а все остальное это массив с Последний раз редактировалось: clicks (2012.07.24 22:49.51), всего редактировалось 1 раз |
Шатунов
Заслуженный писатель
Пол:
Зарегистрирован: 16.07.2007
Сообщения: 2091
Откуда: Оренбургская обл.
Статус: Offline
Заслуженный писатель
Пол:
Зарегистрирован: 16.07.2007
Сообщения: 2091
Откуда: Оренбургская обл.
Статус: Offline
| Спасибо конечно, но очевидно же что этот детский алгоритм не может корректно работать на серьёзных входных данных... +вы сортируете массив из 10^6 пузырьком, а как мы знаем его сложность О(n^2).. при n=10^5 она будет работать около 70 секунд а при 10^6 это будут коллапс, я не могу так долго ждать. меня не устраивает скорость роста квадратичной функции....
Ваш алгоритм валится на простейшем тесте: Входные данные: 1,4,5,6,7,9 Результат работы вашего алгоритма: В = 9,1,4 //9+1+4=14 С = 5,6,7 //5+6+7=18 Как должно быть В = 9,1,6 //9+1+6=16 С = 5,4,7 //5+4+7=16 _________________ Даже когда тебя сожрали у тебя есть два выхода |
| Шатунов
угу, согласен 
подумаю вечерком |
| много времени уделить вечером задаче не удалось, но вот такие выводы
по первому замечанию - про время сортировки, решить другим методом сортировки - это не проблема. важно вот что мой алгоритм, находит в действительности же некое приближение к оптимальному варианту. (ссылку вверху подправил) Найти же полностью оптимальный вариант, пока как методом перебора у меня мыслей нет. Но перебор понятное дело при цифрах 10^6 - это утопия. Пока что тупик. Добавлено спустя 31 минуту 2 секунды: вот что нашел http://www.wikiznanie.ru/ru-wz/index.php/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE%D0%B1_%D0%BE%D0%B4%D0%BD%D0%BE%D0%BC%D0%B5%D1%80%D0%BD%D0%BE%D0%B9_%D0%BE%D0%BF%D1%82%D0%B8%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D0%BE%D0%B9_%D1%83%D0%BF%D0%B0%D0%BA%D0%BE%D0%B2%D0%BA%D0%B5 как я понял полного полиномиального решения пока не придумали, не? |
Шатунов
Заслуженный писатель
Пол:
Зарегистрирован: 16.07.2007
Сообщения: 2091
Откуда: Оренбургская обл.
Статус: Offline
Заслуженный писатель
Пол:
Зарегистрирован: 16.07.2007
Сообщения: 2091
Откуда: Оренбургская обл.
Статус: Offline
clicks писал(а): http://www.wikiznanie.ru/ru-wz/index.php/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE%D0%B1_%D0%BE%D0%B4%D0%BD%D0%BE%D0%BC%D0%B5%D1%80%D0%BD%D0%BE%D0%B9_%D0%BE%D0%BF%D1%82%D0%B8%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D0%BE%D0%B9_%D1%83%D0%BF%D0%B0%D0%BA%D0%BE%D0%B2%D0%BA%D0%B5
Спасибо. Оно самое. clicks писал(а): как я понял полного полиномиального решения пока не придумали, не?Увы пока нет. _________________ Даже когда тебя сожрали у тебя есть два выхода |
| быстрая сортировка исходного массива по убыванию.
далее разброс в 2 массива, по ходу в 2 переменные суммируешь и сравниваешь, если первая больше второго, запись во второй массив нового элемента, иначе в первый |
Шатунов
Заслуженный писатель
Пол:
Зарегистрирован: 16.07.2007
Сообщения: 2091
Откуда: Оренбургская обл.
Статус: Offline
Заслуженный писатель
Пол:
Зарегистрирован: 16.07.2007
Сообщения: 2091
Откуда: Оренбургская обл.
Статус: Offline
| Циник
Шатунов писал(а): Результат работы вашего алгоритма:
В = 9,1,4 //9+1+4=14 С = 5,6,7 //5+6+7=18 Как должно быть В = 9,1,6 //9+1+6=16 С = 5,4,7 //5+4+7=16 _________________ Даже когда тебя сожрали у тебя есть два выхода |
Страница 1 из 1
Список форумов Шадринский форум -> Программирование -> Программирование для школьников и студентов. -> Задача о равномерном распределении чисел
| |
Вы не можете начинать темы Вы не можете отвечать на сообщения Вы не можете редактировать свои сообщения Вы не можете удалять свои сообщения Вы не можете голосовать в опросах Вы не можете вкладывать файлы Вы можете скачивать файлы |