Вот акциз из книги " Руководство по разработке алгоритмов ".
В задаче упаковки в бункер нам дано n металлических предметов, каждый из которых весит от нуля доодин килограммНаша цель состоит в том, чтобы найти наименьшее количество бункеров, в которых будут храниться n объектов, причем каждый бин вмещает не более одного килограмма.
Наилучшая эвристика для упаковки бинов выглядит следующим образом.Рассмотрим объекты в том порядке, в котором они даны. Для каждого объекта поместите его в частично заполненную корзину с наименьшим количеством дополнительной комнаты после того, как объект вставлен .Если такой корзины нет, запустите новую корзину.Разработайте алгоритм, который реализует наиболее подходящую эвристику (принимая в качестве входных данных n весов w1, w2, ..., wn и выводя количество используемых бинов) за время O (nlogn).
Хорошо, этот акциз кажется не сложным.Мое первоначальное понимание состоит в том, что для наилучшего эвристического подхода я просто каждый раз ищу корзину с минимальным доступным пространством и пытаюсь поместить объект внутрь. Если объект не подходит к корзине с минимальным пространством, я создаю новыйbin.
Я могу создать BST для хранения корзин, и каждый раз, когда объект помещается в корзину, я могу удалять эту корзину из дерева, обновлять доступное пространство корзины и повторно вставлять корзину вдерево.Это будет иметь значение O (logN) для каждого размещения объекта.
Однако я заметил жирную и курсивную часть акциза. «Для каждого объекта поместите его в частично заполненную корзину с наименьшим количеством дополнительной комнаты после вставки объекта".
Таким образом, это означает, что я не ищу корзину с минимальным доступным пространством, а я ищу такую, в которой, если я помещу текущий объект, результирующее доступное пространство (после размещения объекта) будетминимум.
Например, если текущее пространство bin1 равно 0.5, bin2 равно 0,7.Таким образом, в настоящее время bin1 является минимальным.Но если текущий объект равен 0,6, то объект не может быть помещен в bin1, вместо создания нового bin, я должен найти bin2, чтобы поместить объект как bin2 - object = 0.7 - 0.5 = 0.2, что в этом случае является минимальным.
Я прав?Смелая часть утверждения действительно означает то, что я думал?Или это так же просто, как «найти корзину с минимальным пространством, если можно поместить объект, а затем поместить; если не удается, то создать новую корзину»?
Спасибо
Править: добавление части моего кода Java для моего нового понимания жирной части.
public void arrangeBin(float[] w) {
BST bst = new BST();
bst.root = new Node();
int binCount = 0;
for (int i = 0;i < w.length;i++) {
float weight = w[i];
Node node = bst.root;
float minDiff = 1;
Node minNode = null;
while(node!=null) {
if (node.space > weight) {
float diff = node.space - weight;
if (minDiff > diff) {
minDiff = diff;
minNode = node;
node = node.left;
}
}
else
node = node.right;
}
if (minNode == null) {
binCount++;
Node node = new Node();
node.space -= weight;
bst.insert(node);
}
else {
minNode.space -= weight;
bst.delete(minNode);
bst.insert(minNode);
}
}
}