- Bin-đóng gói, sắp xếp thùng để đóng gói các đối tượng n

Question

Dưới đây là một đoạn trích từ cuốn sách "Algorithm Design Manual".

Trong vấn đề đóng gói bin, chúng tôi được cung cấp các vật thể kim loại n, mỗi vật nặng từ 0 đến 1 kg. Mục tiêu của chúng tôi là tìm số lượng thùng nhỏ nhất sẽ giữ n đồ vật, với mỗi thùng chứa tối đa một kilôgam.

Phương pháp phỏng đoán phù hợp nhất để đóng gói thùng rác như sau. Xem xét các đối tượng theo thứ tự mà chúng được đưa ra. Đối với mỗi đối tượng, đặt vào thùng chứa một phần với số tiền nhỏ nhất thêm phòng sau khi đối tượng được lắp. Nếu không có thùng rác như vậy, hãy bắt đầu một thùng mới . Thiết kế một thuật toán thực hiện các heuristic phù hợp nhất (lấy làm đầu vào n trọng lượng w1, w2, ..., wn và xuất số của thùng được sử dụng) trong O (nlogn) thời gian.

Ok, sự kiện này có vẻ không khó. Sự hiểu biết ban đầu của tôi là cho phương pháp tiếp cận heuristic phù hợp nhất, tôi chỉ cần mỗi lần tìm một cái thùng với khoảng trống tối thiểu và cố gắng đặt vật thể vào. Nếu vật thể không vừa với thùng với không gian tối thiểu, tôi tạo ra một cái mới bin.

Tôi có thể xây dựng một BST để lưu trữ thùng và mỗi khi một vật được đưa vào thùng, tôi có thể xóa thùng rác đó khỏi cây, cập nhật không gian sẵn có của thùng và lắp lại thùng vào cây. Điều này sẽ chính O (logN) cho mọi vị trí đối tượng.

Tuy nhiên, tôi nhận thấy phần in đậm và nghiêng của đoạn trích "Đối với từng đối tượng, đặt nó vào thùng chứa một phần với số lượng phòng nhỏ nhất sau khi đối tượng được chèn". Vì vậy, điều này có nghĩa là tôi không tìm kiếm một thùng có dung lượng trống tối thiểu, thay vào đó, tôi đang tìm một cái nếu tôi đặt đối tượng hiện tại vào, khoảng trống có sẵn (sau khi đặt đối tượng) sẽ ở mức tối thiểu.

Ví dụ: nếu không gian hiện tại của bin1 là 0,5, thì bin2 là 0,7. Vì vậy, hiện tại, bin1 là mức tối thiểu. Nhưng nếu đối tượng hiện tại là 0,6, thì đối tượng không thể được đặt vào bin1, thay vì tạo một thùng mới, tôi phải tìm bin2 để đặt đối tượng là bin2 - object = 0.7 - 0.5 = 0.2, sau đó tối thiểu.

Tôi có đúng không? Phần táo bạo của câu nói có thực sự có ý nghĩa như những gì tôi nghĩ không? Hay đơn giản là "tìm một cái thùng với không gian tối thiểu, nếu có thể đặt vật thể, rồi đặt vào chỗ đó, nếu không thể, thì hãy tạo một cái thùng mới"?

Cảm ơn

Chỉnh sửa: thêm một phần mã java của tôi cho sự hiểu biết mới về phần in đậm.

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); 
     } 
    } 
} 

Answer 1

Tuyên bố in đậm thực sự có ý nghĩa như bạn nghĩ.

Ý tưởng sẽ là tìm thùng đầy đủ nhất đối tượng hiện tại sẽ vừa với, do đó giảm thiểu lượng không gian lãng phí. Nếu đối tượng không phù hợp với bất kỳ thùng nào thì cần phải tạo thùng mới

Answer 2

Bạn cần giữ một mảng được sắp xếp trong đó trong O (log (n)) và chèn lại vào cây cũng trong O (log (n)). Quan sát của bạn có vẻ đúng - bạn cần phải tìm cái thùng phù hợp nhất với trọng lượng mới của bạn. Hi vọng điêu nay co ich.