Алгоритм укладки ящиков

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

Вот мой подход:

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

Я также, возможно, думаю, что это очевидная проблема динамического программирования, которая возникает у меня над головой. Любая помощь будет оценена

Источник

2 ответа

Решение

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

Вместо того, чтобы рассматривать конкретные операции, которые могут происходить в столбце, давайте посмотрим на процесс в целом. Изначально у нас есть данный столбец. В конце у нас есть результирующий столбец. Что осталось от данного столбца в результирующем столбце? Это подпоследовательность (поскольку мы можем удалить ящик из любого места) данного столбца, который передан префиксу результирующего столбца ("префикс", как в "расположенном внизу"), поскольку мы можем добавлять новые поля только поверх что там было изначально).

Естественно, мы хотим максимизировать длину этой последовательности (подпоследовательность или префикс, в зависимости от того, где вы смотрите). Это, конечно, похоже на проблему динамического программирования, похожую на расстояние редактирования или самую длинную общую подпоследовательность. Возможно, вы захотите проработать детали самостоятельно с этого момента. Удачи!

Источник

Конечно, вы можете работать по одному столбцу за раз.

Затем преобразовать столбец [x1, x2, x3, ...] в столбец [y1, y2, y3, ...] у вас есть несколько случаев:

  • дело (А): x1 такой же как y1: это простой случай, вам нужно соответствовать остальным
  • дело (B): x1 является - а также y1 нет: нужно все остальное вставить y ящики
  • дело (с): y1 является - а также x1 нет: нужно удалить все остальные x ящики
  • дело (D): x1 а также y1 не пустые, а разные; здесь вы должны выбрать между: (D1) флип x1 и соответствовать [x2,...] с [y2,...], (D2) удалить x1 и соответствовать [x2, ...] с [y1, ...], Вы должны выбрать (D1) или (D2) в зависимости от того, какой из них требует меньше операций.

Примечание: опция (D3) вставки y1 в x и соответствие [x1,...] с [y2,...] не доступно, учитывая правила, потому что вы можете добавить только коробки в верхней части стопки (случай B).

Это переводится в алгоритм динамического программирования (или рекурсии с запоминанием):

int min_moves(int i, int j);

и вам нужно вычислить количество ходов, чтобы выровнять столбец x[i], x[i+1], ... в столбец y[j], y[j+1], ... где x а также y исходное содержимое двух манифестов, считанных из файла, при условии, что x[i] а также y[i] быть - для любого i>m,

Вычислить min_moves(i, j) ты можешь использовать min_moves(i+1, j+1) (случаи A + D1), min_moves(i+1, j) (дело D2). Случаи B и C не требуют рекурсии, но являются прямым вычислением x а также y,

Источник
Другие вопросы по тегам