Nối n dây với chi phí tối thiểu (Connect n ropes with minimum cost)

Giới thiệu

Có N đoạn dây với độ dài cho trước. Ta phải nối chúng lại với nhau. Chi phí nối một dây với dây khác là tổng độ dài của chúng. Mục tiêu là nối N dây với chi phí tối thiểu.

Bài toán này có thể giải quyết bằng cây heap (heap tree). Ta sẽ tạo min-heap để chèn tất cả các độ dài khác nhau, sau đó lấy phần tử nhỏ nhất và nhỏ thứ hai từ min-heap, nối chúng và lại chèn vào cây heap. Khi heap chỉ còn một phần tử, ta có thể dừng quá trình và có dây đã nối với chi phí tối thiểu.

Đầu vào và Đầu ra

Đầu vào: Độ dài các dây: {4, 3, 2, 6, 5, 7, 12}
Đầu ra: Tổng chi phí tối thiểu: 103

Thuật toán

findMinCost(array, n)
Đầu vào: Danh sách độ dài dây, số lượng mục trong danh sách.
Đầu ra: Chi phí tối thiểu để cắt.

Begin
    minCost := 0
    điền priority queue với các phần tử mảng (giá trị lớn hơn có độ ưu tiên cao hơn)
    while queue không rỗng, do
        item1 := lấy mục từ queue và xóa khỏi queue
        item2 := lấy mục từ queue và xóa khỏi queue
        minCost := minCost + item1 + item2
        thêm (item1 + item2) vào queue
    done
    return minCost
End

Ví dụ (C++)

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int findMinimumCost(int arr[], int n) {
    // priority queue được thiết lập là giá trị lớn hơn có độ ưu tiên cao hơn
    priority_queue<int, vector<int>, greater<int>> queue(arr, arr+n);
    int minCost = 0;
    while (queue.size() > 1) {  // khi queue có nhiều hơn một phần tử
        int item1 = queue.top();  // item1 là phần tử ngắn nhất
        queue.pop();
        int item2 = queue.top();  // item2 lớn hơn item1 nhưng ngắn hơn các cái khác
        queue.pop();
        minCost += item1 + item2;  // nối dây và thêm vào queue
        queue.push(item1 + item2);
    }
    return minCost;
}

int main() {
    int ropeLength[] = {4, 3, 2, 6, 5, 7, 12};
    int n = 7;
    cout << "Total minimum cost: " << findMinimumCost(ropeLength, n);
}

Kết quả

Total minimum cost: 103