|
0 / 0 / 0
Регистрация: 08.05.2016
Сообщений: 73
|
|
Приближенный алгоритм. Грузовики и камни16.05.2017, 15:36. Показов 1359. Ответов 1
Метки нет (Все метки)
Подскажите алгоритм, ибо мой не проходит по времени(ограничения 1 секунда).
Я делал так: сортировал грузовики и камни и последовательно шел по массиву грузовиков и пробовал запихивать камень, если он не пихался, то шел по массиву камней так до конца. Второй метод: отсортил камни и грузовики и в этот раз, если камень не пихется, то ищем в массиве камней наиболее подходящий камень за logN( постоянно разделяя массив камней на 2 подмассива и брал тот, в котором должен быть камень, который поместиться в машину) Все 2 алгоритма не проходят по времени. Подскажите, может кто уже решал такие задачи? Имеется n камней и m машин в очереди. Камни характеризуются массой, машины — грузоподъемностью. Необходимо определить порядок загрузки, при котором минимизируется число используемых машин. Замечание Известно, что любой камень помещается в любую машину, а также, что если искомое размещение существует, то общее число машин не менее чем вдвое превосходит минимально возможное число машин. Формат входного файла В первой строке находится число m грузовиков (1 ≤ m ≤ 300 000). В следующих m строках записаны грузоподъёмности грузовиков. В следующей строке находится число n камней (1 ≤ n ≤ 300 000). Далее в n строках записаны массы камней. Формат выходного файла Если решение существует, то выведите 2m + 1 строк. В первой — число m, а далее для каждой машины в первой строке должна находиться грузоподъёмность грузовика, а во второй — последовательно через пробел массы камней, положенных в грузовик (пустая строка, если в грузовик ничего не положено). Число используемых машин не должно превышать минимально возможное более чем в два раза. Если решений нет, то выведите no solution.
0
|
|
| 16.05.2017, 15:36 | |
|
Ответы с готовыми решениями:
1
Фильм-обзор об играх про грузовики
|
|
0 / 0 / 0
Регистрация: 08.05.2016
Сообщений: 73
|
||||||
| 21.05.2017, 19:44 [ТС] | ||||||
|
Так долго не отвечали, что пришлось самому решить(
First-fit algorithm This is a very straightforward greedy approximation algorithm. The algorithm processes the items in arbitrary order. For each item, it attempts to place the item in the first bin that can accommodate the item. If no bin is found, it opens a new bin and puts the item within the new bin. It is rather simple to show this algorithm achieves an approximation factor of 2, that is, the number of bins used by this algorithm is no more than twice the optimal number of bins. In other words, it is impossible for 2 bins to be at most half full because such a possibility implies that at some point, exactly one bin was at most half full and a new one was opened to accommodate an item of size at most V/2. But since the first one has at least a space of V / 2, the algorithm will not open a new bin for any item whose size is at most V / 2. Only after the bin fills with more than V / 2 or if an item with a size larger than V / 2 arrives, the algorithm may open a new bin. Thus if we have B bins, at least B − 1 bins are more than half full. Therefore, {\displaystyle \sum _{i=1}^{n}a_{i}>{\tfrac {B-1}{2}}V} \sum_{i=1}^n a_i>\tfrac{B-1}{2}V. Because {\displaystyle {\tfrac {\sum _{i=1}^{n}a_{i}}{V}}} \tfrac{\sum_{i=1}^n a_i}{V} is a lower bound of the optimum value OPT, we get that B − 1 < 2OPT and therefore B ≤ 2OPT.[6] See the analysis below for better approximation results.
0
|
||||||
| 21.05.2017, 19:44 | |
|
Помогаю со студенческими работами здесь
2
Приближенный двоичный поиск
ADOTable.Locate, приближенный поиск Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
Новые блоги и статьи
|
|||
|
моя боль
iceja 24.01.2026
Выложила интерполяцию кубическими сплайнами www. iceja. net
REST сервисы временно не работают, только через Web.
Написала за 56 рабочих часов этот сайт с нуля. При помощи perplexity. ai PRO , при. . .
|
Модель сукцессии микоризы
anaschu 24.01.2026
Решили писать научную статью с неким РОманом
|
http://iceja.net/ математические сервисы
iceja 20.01.2026
Обновила свой сайт http:/ / iceja. net/ , приделала Fast Fourier Transform экстраполяцию сигналов. Однако предсказывает далеко не каждый сигнал (см ограничения http:/ / iceja. net/ fourier/ docs ). Также. . .
|
http://iceja.net/ сервер решения полиномов
iceja 18.01.2026
Выкатила http:/ / iceja. net/ сервер решения полиномов (находит действительные корни полиномов методом Штурма).
На сайте документация по API, но скажу прямо VPS слабенький и 200 000 полиномов. . .
|
|
Расчёт переходных процессов в цепи постоянного тока
igorrr37 16.01.2026
/ *
Дана цепь(не выше 3-го порядка) постоянного тока с элементами R, L, C, k(ключ), U, E, J. Программа находит переходные токи
и напряжения на элементах схемы классическим методом(1 и 2 з-ны. . .
|
Восстановить юзерскрипты Greasemonkey из бэкапа браузера
damix 15.01.2026
Если восстановить из бэкапа профиль Firefox после переустановки винды, то список юзерскриптов в Greasemonkey будет пустым.
Но восстановить их можно так.
Для этого понадобится консольная утилита. . .
|
Сукцессия микоризы: основная теория в виде двух уравнений.
anaschu 11.01.2026
https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/
|
WordPad для Windows 11
Jel 10.01.2026
WordPad для Windows 11
— это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .
|