Алгоритм заполнения слотов - PullRequest
Новая
       31

Алгоритм заполнения слотов

5 голосов
/ 26 мая 2010

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

  • Текущие уровни и доступное количество для заполнения известны
  • Результирующие уровни должны быть как можно более равными, но существующий уровень не может быть уменьшен
  • Слоты заполнены слева направо, поэтому левые слоты получают более высокий уровень, если равный уровень невозможен

Примеры http://img695.imageshack.us/img695/6529/fill.png

На рисунке выше показано шесть примеров, каждый столбец представляет собой слот. Серая область уже заполнена, синяя - это ожидаемое положение новых элементов.

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

Я собираюсь реализовать это с помощью SQL / PL/SQL, другой код также приветствуется:)

Ответы [ 4 ]

2 голосов
/ 26 мая 2010

Это довольно просто.

Вы можете визуализировать это как налив воды и дайте ей наполниться, за исключением некоторых случаев *.

  1. Сортировка. Вы также можете использовать приоритетную очередь.
  2. Отслеживать количество текущих минимальных столбцов.
  3. Получить столбец min со вторым столбцом min.
  4. Заполните столбец min количеством доступных элементов или до второго столбца min.
  5. Увеличение количества текущих минимальных столбцов.
  6. Переходите к шагу 4 до тех пор, пока все столбцы не будут на одном уровне, за исключением того, что используется количество доступных элементов или дельта (вторая минута - первая минута), умноженная на количество текущих минимальных столбцов. Если количество доступных элементов недостаточно, просто выполните простую математику (деление и остаток), чтобы заполнить столбцы, и используйте остаток для заполнения слева.
  7. Когда все столбцы находятся на одном уровне, используйте простую математическую часть, описанную в шаге 6.

Ты должен быть хорошим.

Этот алгоритм работает за O( n log n ) времени.

* В некоторых случаях это не имеет смысла, но вы все равно захотите это сделать: 

 #
 #
##
###
###

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

1 голос
/ 26 мая 2010

Возможно, достаточно жадного алгоритма с рандомизацией для разрыва связей.

Пусть n будет количеством слотов, которое нужно заполнить.

Шаг 1: Прокрутите столбцы, чтобы определить столбцы, у которых меньше всего заполненных слотов. Пропустить уже заполненные столбцы.

Шаг 2: Если ни один из столбцов не определен на шаге 1, больше, чем один, то выберите один из них случайным образом.

Шаг 3: Установите n = n-1

Повторяйте шаги 1, 2 и 3 до тех пор, пока n = 0 или у вас нет пустых столбцов.

0 голосов
/ 27 мая 2010
  1. Сортировка столбцов с самого низкого до самого высокого начального уровня.
  2. Рассчитать совокупное начальное использование для (отсортированных) столбцов.
  3. Вычислить для каждого столбца, сколько будет использоваться новая заливка, заполнив ее до высоты этого столбца. Используемой суммой будет высота столбца, умноженная на индекс столбца, минус совокупное начальное использование всех столбцов перед ним.
  4. Выберите столбец с индексом i, который будет использовать большую часть вашей новой заливки, не переходя. Заполните все столбцы вплоть до столбца i до высоты столбца i (который будет использовать объем заполнения, вычисленный на шаге № 3 для столбца i), затем оставшаяся заливка будет равномерно распределена по первым столбцам i floor(remaining / i) плюс одна дополнительная заливка первые remaining % i столбцы.
  5. Отмена сортировки столбцов для получения результата.

Это должно занять линейное время в количестве столбцов (независимо от количества заполнения).

0 голосов
/ 26 мая 2010

Звучит как классическая проблема с рюкзаком Для этого существует множество различных языковых решений с использованием разных алгоритмов на Rosetta Code , хотя я не уверен, что в PL / SQL

...