Нахождение идеального использования арендуемых предметов в рубине - PullRequest
Новая
       4

Нахождение идеального использования арендуемых предметов в рубине

1 голос
/ 27 января 2010 
# Jan, Feb, Mar, Apr, May, Jun, Jul, Aug, Sep, Oct, Nov, Dec
rentable_items = [ 
  %w(x x x - - - x x x - - -), # item1
  %w(- - - - - - - - - - - -), # item2
  %w(x x x x x x x - - - - -), # item3
  %w(x x x - - - - x x x x x) ]# item4

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

Когда я получаю входящий запрос на период с апреля по июнь, я хочу получить результат в следующем порядке: 

items = rentable_items.ideal_utilization_for("2010/03/01", "2010/06/30")
items # [item1, item2, item4] #where item4 is the worst

Идея заключается в том, чтобы сначала заполнить пробелы в предмете и попытаться создать как можно меньше новых пробелов.

Мне не нужно полное решение, но совет, какие инструменты (библиотека, гем, алогритм) доступны для такой проблемы. Примеры будут очень признательны.

[Редактировать: удален второй пример, чтобы сосредоточиться на реальной проблеме.]

1 Ответ

1 голос
/ 28 января 2010

Я хочу получить предметы с наименьшим количеством обменов по пунктам ... арендная плата поступает один за другим.

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

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

Если люди могут зарезервировать предметы, подождите до дня, чтобы назначить им предметы, а затем назначьте их от самого короткого до самого длинного.

Это, конечно, только один ответ; есть буквально бесконечно много эвристик, которые вы могли бы применить.

...