Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.60/5: Рейтинг темы: голосов - 5, средняя оценка - 4.60
оранжевая мышь
0 / 0 / 0
Регистрация: 20.02.2018
Сообщений: 4
1

Быстрый поиск пар

20.02.2018, 19:25. Просмотров 857. Ответов 4

Здравствуйте.

Задача такая: есть N прямоугольных "коробок" и N прямоугольных "вещей" (все они заданы парами ширина-высота, поворачивать нельзя), нужно для каждой вещи найти коробку, в которую она поместится, если такая существует (то есть, в конце могут остаться неупакованные вещи и пустые коробки, и их количество не обязано быть минимальным возможным (хотя было бы здорово), но среди них уже должно быть нельзя что-то куда-то поместить; в одну коробку нельзя класть больше одной вещи).

Например, если есть коробки 3х3, 4х6 и 1х5 и вещи 2х2, 3х4 и 1х1, решение "2х2 кладём в 4х6, 1х1 -- в 1х5, коробка 3х3 и вещь 3х4 остаются" корректно.

Можно ли решить задачу гарантированно быстрее, чем за N2? В идеале за NlogN.

За квадрат перебором понятно как.
Ещё можно "коробки" хранить в декартовом дереве (которое будет деревом поиска по ширине и кучей по высоте или наоборот), и по очереди для каждой вещи искать коробку, тогда иногда нам будет везти, и алгоритм будет работать за NlogN -- но в худшем случае имеем тот же N2, не годится.
0
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
20.02.2018, 19:25
Ответы с готовыми решениями:

Быстрый поиск слова
Поделитесь кто-нибудь знаниями по быстрому поиску в большом объеме текста, находящемся в памяти....

Быстрый поиск папок на сервере
Здравствуйте! Задача: Есть сервер. На сервере хранятся определенные папки с файлами. Имя такой...

Быстрый поиск k ближайших соседей
Имеется 10000 точек в 20-мерном пространстве. Распределены более менее равномерно. Нужно по...

Быстрый поиск элементов массива
Есть два частично заполненных трёхмерных массива. Массивы не ограничены по размерности (т.е....

Быстрый поиск строки в списке строк с предварительным хешированием
Здравствуйте. Необходимо реализовать быстрый поиск строки в списке строк с предварительным...

4
Shamil1
Модератор
2257 / 1540 / 351
Регистрация: 26.03.2015
Сообщений: 5,497
21.02.2018, 17:13 2
Лучший ответ Сообщение было отмечено оранжевая мышь как решение

Решение

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
boxes = [(3,3), (4,6), (1,5)]
items = [(2,2), (3,4), (1,1)]
 
def solve(boxes, items):
    boxes.sort()
    items.sort()
    res, t = [], []
    i, cnt = 0, len(items)
    for box in boxes:
        # add candidates to the tree
        while i < cnt and items[i][0] <= box[0]:
            t.append(items[i])
            i += 1
        # select the best candidate
        item =  max((x for x in t if x[1] <= box[1]), key=lambda x: x[1], default=False)
        if item:
            res.append((box, item))  # put the item to the box
            t.remove(item)           # remove the item from candidates
    return res, t
        
print(solve(boxes,items))
1. Сортируем коробки и вещи по высоте.
2. Для каждой коробки:
2.1. Добавляем в буфер все вещи, которые входят по высоте
2.2. Выбираем из буфера вещь с максимальной шириной, которая входи в коробку. Если такая вещь есть, достаём её из буфера и кладём в коробку

В качестве буфера я использовал список. Надо использовать дерево (Self-balancing binary search tree). Тогда операции append, max, remove будут выполняться за logN и весь алгоритм будет работать за NlogN.
1
оранжевая мышь
0 / 0 / 0
Регистрация: 20.02.2018
Сообщений: 4
21.02.2018, 17:34  [ТС] 3
Цитата Сообщение от Shamil1 Посмотреть сообщение
2. Для каждой коробки:
2.1. Добавляем в буфер все вещи, которые входят по высоте
Уже квадрат в худшем случае.
0
Shamil1
Модератор
2257 / 1540 / 351
Регистрация: 26.03.2015
Сообщений: 5,497
21.02.2018, 20:48 4
Цитата Сообщение от оранжевая мышь Посмотреть сообщение
Уже квадрат в худшем случае.
Не квадрат, а NlogN. Каждую коробку мы добавим не больше одного раза.
0
оранжевая мышь
0 / 0 / 0
Регистрация: 20.02.2018
Сообщений: 4
23.02.2018, 11:19  [ТС] 5
Точно, буфер же на каждой итерации пополняется, а не заполняется с нуля, извините.

Спасибо!
0
23.02.2018, 11:19
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
23.02.2018, 11:19

Быстрый поиск значения в строке по заранее изветному ключу
Привет! Есть задача: Строка данных содержит в себе пары ключ:значение, и имеет вид: ...

Самый быстрый перебор пар чисел
Задача: Есть число N. Найти все пары чисел от 1 до N, которые в сумме дают M. Можно так: for...

Система "Быстрый пар"
Слышал о том, что в кофеварках есть система &quot;Быстрый пар&quot;. Прошу объяснить, что она дает и каков...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
5
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru