Что это за комп. Sci. Проб. называется?

Question

Я думал об этой проблеме с некоторыми реальными случаями использования, но поскольку я понятия не имею, что она называется, я не могу найти никакой информации об этом. Если он напоминает какую-то известную проблему компьютерной науки, кто-то другой, вероятно, сделал лучшее решение, чем я.

У меня есть куча lego, содержащая кирпичи различных видов. Там может быть любое количество кирпичей любого типа. У меня также есть набор дизайнов/вещей, которые я мог бы построить с помощью lego, каждый из которых содержит список необходимых частей.

Что я могу построить с моей кучей lego? (по одному)

Answer 1

Это проблема запроса многомерного диапазона. Если k - количество типов кирпича, то каждая конструкция может быть представлена ​​k-мерной точкой (массив length-k), координаты которой являются требуемыми числами каждого типа кирпича, и то, что вы ищете, - это набор всех точек в базе данных, имеющих координаты меньше соответствующих координат точки запроса (x_1, ..., x_k), что соответствует вашей куче. Другой способ сказать это в том, что вы ищете множество точек в гиперпрямом, ограниченном (0, ..., 0) - (x_1, ..., x_k).