Проблема упаковки: элементы в ограниченные ячейки (решение единственной матрицы) - PullRequest
Новая
       15

Проблема упаковки: элементы в ограниченные ячейки (решение единственной матрицы)

1 голос
/ 13 июня 2019

РЕДАКТИРОВАТЬ: способ, которым я пытался решить эту проблему с одновременными уравнениями, может на самом деле не работать, любые другие подходы будут оценены.

У меня есть набор контейнеров, каждый с максимальной емкостью n, инабор типов элементов, которые они могут содержать.

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

EG: 

Bin 0, capacity 2, item types stored (b,d)
Bin 1, capacity 3, item types stored (b,c)
Bin 2, capacity 2, item types stored (c,d)

Попытка сохранить 3d,2c, 2b - успех: Bin 0-dd, Bin 1-cbb, Bin 2-dc.

Мне нужно в качестве выхода решение, если существует один / много, или ноль, если решения не существует.

ПРИМЕЧАНИЕ: нет ограничений по количеству типов элементов, которые может хранить корзина, или по общему количеству элементов.

Я пытался построить линейные уравнения одновременности и использовать JAMA для их решения, однако матрица не является единственной, что, я думаю, означает бесконечные решения / никаких решений.Если есть бесконечные решения, то мне просто нужно одно из них.

    EG I get these equations
    d0 + d2 = 3
    b0 + b1 = 2
    c1 + c2 = 2
    b0 + d0 = 2
    b1 + c1 = 3
    c2 + d2 = 2
    with these variables
    [d0, d2, c1, c2, b0, b1] where d0 is the number of d in bin 0

    Leading to these arrays LHS
    [1.0, 1.0, 0.0, 0.0, 0.0, 0.0],
    [0.0, 0.0, 0.0, 0.0, 1.0, 1.0],
    [0.0, 0.0, 1.0, 1.0, 0.0, 0.0],
    [1.0, 0.0, 0.0, 0.0, 1.0, 0.0], 
    [0.0, 0.0, 1.0, 0.0, 0.0, 1.0],
    [0.0, 1.0, 0.0, 1.0, 0.0, 0.0]]

   RHS
   [3.0, 2.0, 2.0, 2.0, 3.0, 2.0]

    Matrix lhs = new Matrix(lhsArray);
    Matrix rhs = new Matrix(rhsArray, rhsArray.length);
    Matrix ans = lhs.solve(rhs);

Я получаю сообщение о том, что массив является единственным.Это не значит, что это неразрешимо, не так ли?Поскольку решение d0 = 2, c1 = 1, b1 = 2, d2 = 1, c2 = 1 решает его.

1 Ответ

0 голосов
/ 13 июня 2019

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

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

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

Edit: в вашем примере алгоритм будет сортировать ваши элементы в 3d, 2b, 2c. Затем он проверит емкость d, которая будет 4 (2 из корзины 0, 2 из корзины 2). Затем он помещает ваши элементы типа 3 d, 2 в 0, 1 в 2. Далее он рассматривает 2b. Оставшаяся емкость равна 3 (из корзины 1), поэтому он помещает оба элемента в корзину 1. Наконец, он учитывает 2c. Общая вместимость составляет 2 (1 остается в бункере 1, а 1 - в бункере 2). Он размещает эти элементы соответственно, и теперь ваш список пуст, поэтому он возвращает единственное решение (корзина 0: 2d; корзина 1: 2b, 1c; корзина 2: 1d, 1c).

Другой пример, показывающий перераспределение:

Бункер 0, емкость 2 (б, д) Бункер 1, емкость 3 (с, д) Бункер 2, емкость 2 (б, в)

Предметы: 4d, 3b

Первоначально выделите 2 d для корзины 0, а остальные 2 - для корзины 1.

Теперь у нас проблема - у нас есть 3b и только 2 открытых емкости (в корзине 2).

Затем алгоритм находит полные контейнеры, которые могут содержать b, который является только бином 0, и пытается перераспределить 1 из элементов типа d там. Это может быть сделано, потому что корзина 1 все еще имеет 1 открытую емкость и может содержать тип d (но не b), и теперь у нас есть доступная емкость в корзине 0 для оставшегося элемента типа b.

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

...