여기에 책 "Algorithm Design Manual"의 소비재가 있습니다.알고리즘 - 빈 패킹, n 개의 객체를 포장하기위한 빈 배열
빈 포장 문제에는 각각 무게가 0 - 1kg 인 n 개의 금속 물체가 제공됩니다. 우리의 목표는 n 개의 물체를 담을 수있는 가장 작은 수의 수납함을 찾는 것입니다. 각 수납기는 최대 1kg을 가지고 있습니다.
빈 패킹에 가장 적합한 휴리스틱은 다음과 같습니다. 주어진 순서대로 개체를 고려하십시오. 각 개체의 경우 을 개체가 삽입 된 후 실 의 가장 작은 양으로 채 웁니다.. 해당 bin이 없으면 새 bin을 시작하십시오. O (nlogn) 시간에 가장 적합한 경험적 방법 인 (n 개의 가중치 w1, w2, ..., wn을 입력으로 사용하고 빈의 수인 을 출력)을 구현하는 알고리즘을 설계하십시오.
좋아,이 소비세는 어렵지 않다. 필자가 처음으로 알아야 할 점은 가장 적합한 휴리스틱 접근 방법 인 경우, 항상 빈 공간이 최소 인 빈을 찾아 객체를 넣으려고한다는 것입니다. 객체가 최소 공간이있는 빈에 맞지 않으면 새로운 큰 상자.
빈을 저장할 BST를 만들 수 있으며 개체를 빈에 넣을 때마다 트리에서 해당 빈을 삭제하고 빈의 사용 가능한 공간을 업데이트 한 다음 트리에 해당 빈을 다시 삽입 할 수 있습니다. 이것은 모든 오브젝트 배치에 대해 O (logN)를 보냅니다.
단, I는 "개체를 삽입 한 후 여분의 공간 최소량으로 부분적으로 채워진 빈에 배치, 각 개체"소비세의 굵은 이탤릭체 부분 차렸다.
그래서 현재 사용 가능한 공간이 가장 적은 빈을 찾고 대신 객체를 배치 한 후 사용 가능한 공간이 최소가되는 빈을 찾고 있습니다.
예를 들어 bin1의 현재 공간이 0.5이면 bin2는 0.7입니다. 따라서 현재 bin1이 최소값입니다. 그러나 현재 객체가 0.6이면 새 빈을 만드는 대신 객체를 bin1에 배치 할 수 없습니다. 객체를 bin2 - object = 0.7 - 0.5 = 0.2로 설정해야 bin2를 찾아야합니다.
맞습니까? 진술의 굵은 부분은 내가 생각했던 것과 같은 의미입니까? 아니면, "최소한의 공간을 가진 빈을 찾은 다음, 객체를 놓을 수 있다면 배치하고, 그렇지 않으면 새 빈을 만듭니다"와 같이 간단합니까?
감사
편집 : 굵은 부분의 나의 새로운 이해 내 자바 코드의 일부를 추가.
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);
}
}
}
코드가 실행될 때마다 모든 노드를 지나치므로 실행 시간이 O (N2)가됩니다. O (nlogn)를 얻고 싶다면 내 답변에서 제안한 것과 같은 것을 사용해야합니다. 그것보다 옳은 것 같아. – WeaselFox
@WeaselFox, 대담한 진술에 따르면, –