Bài toán về chiếc ba lô phân số: Thuật toán tham lam với ví dụ

Chiến lược tham lam là gì?

Thuật toán tham lam Chọn phương án tối ưu cục bộ tốt nhất ở mỗi bước với hy vọng rằng một chuỗi các điểm tối ưu cục bộ sẽ tạo ra một giải pháp tối ưu toàn cục. Giống như Lập trình động, chúng nhắm đến các bài toán tối ưu hóa, nhưng chúng không bao giờ xem xét lại các quyết định trước đó.

Các thuật toán tham lam thường dễ viết, nhanh (thường là thời gian tuyến tính hoặc bậc hai), dễ gỡ lỗi và tốn ít bộ nhớ. Nhược điểm là kết quả không phải lúc nào cũng tối ưu, vì vậy chiến lược này chỉ hiệu quả đối với các bài toán đã được chứng minh là có cấu trúc an toàn khi sử dụng thuật toán tham lam.

Các chiến lược tham lam giải quyết bài toán tối ưu tổ hợp bằng cách xây dựng lời giải A từng thành phần Ai một. Ở mỗi bước, bạn chọn Ai tối ưu nhất theo các ràng buộc hiện tại và thu nhỏ bài toán thành một bài toán con nhỏ hơn.

Để một phương pháp tham lam được coi là chính xác, cần phải có hai điều kiện sau:

1. Thuộc tính lựa chọn tham lam: Việc tìm ra điểm tối ưu cục bộ ở mỗi bước sẽ dẫn đến điểm tối ưu toàn cục. Sự lựa chọn phụ thuộc vào các quyết định trong quá khứ nhưng không phụ thuộc vào các quyết định trong tương lai.
2. Cấu trúc phụ tối ưu: Giải pháp tối ưu cho toàn bộ bài toán bao gồm các giải pháp tối ưu cho các bài toán con của nó.

Thuật toán tham lam có năm thành phần:

1. Một tập hợp các ứng viên được dùng làm cơ sở để xây dựng các giải pháp.
2. Một hàm lựa chọn nhằm tìm ra ứng viên tiếp theo tốt nhất.
3. Một hàm khả thi kiểm tra xem ứng viên có thể mở rộng giải pháp một phần hiện tại hay không.
4. Hàm mục tiêu đánh giá giá trị của một giải pháp hoàn chỉnh hoặc một phần.
5. Một hàm đánh giá báo hiệu khi quá trình giải quyết hoàn tất.

Ý tưởng của kẻ tham lam

Kẻ Tham Lam chỉ sắp xếp các gói hàng theo giá trị:

• Sắp xếp các gói hàng theo thứ tự giá trị giảm dần.
• Duyệt qua danh sách đã được sắp xếp và thêm từng gói hàng vào ba lô nếu dung lượng còn lại cho phép.

Quy tắc này không phải lúc nào cũng đưa ra câu trả lời tối ưu. Ví dụ phản chứng:

• Tham số: n = 3, M = 19.
• Các gói hàng: {i = 1; W = 14; V = 20}, {i = 2; W = 6; V = 16}, {i = 3; W = 10; V = 8} — giá trị cao nhưng cũng có trọng lượng cao.
• Người tham lam chọn gói hàng số 1 với tổng giá trị là 20, trong khi lựa chọn tối ưu (gói hàng số 2, gói hàng số 3) đạt tổng giá trị là 24.

Ý tưởng của Greedy Two

Công ty Greedy Two chỉ phân loại hàng hóa theo trọng lượng:

• Sắp xếp các kiện hàng theo thứ tự trọng lượng không giảm dần.
• Duyệt qua danh sách đã được sắp xếp và thêm từng gói hàng vào ba lô nếu dung lượng còn lại cho phép.

Quy tắc này cũng không tối ưu. Ví dụ phản chứng:

• Tham số: n = 3, M = 11.
• Các gói: {i = 1; W = 5; V = 10}, {i = 2; W = 6; V = 16}, {i = 3; W = 10; V = 28} — trọng lượng nhẹ nhưng giá trị thấp.
• Phương án tham lam chọn hai gói (gói 1, gói 2) với tổng giá trị là 26, trong khi lựa chọn tối ưu (gói 3) đạt 28.

Ý tưởng của Greedy Three

Thuật toán Tham lam Ba (Greedy Three) khắc phục cả hai nhược điểm bằng cách kết hợp giá trị và trọng lượng thành một khóa xếp hạng duy nhất. Đây là phương pháp tiêu chuẩn cho Bài toán Ba lô Phân số (Fractional Knapsack Problem).

• Tính chi phí đơn vị V[i] / W[i] cho mỗi gói hàng.
• Sắp xếp các gói hàng theo thứ tự giá thành đơn vị không tăng dần.
• Duyệt qua danh sách đã được sắp xếp và thêm từng gói hàng nếu dung lượng còn lại cho phép.

Thuật toán Tham Lam Ba sắp xếp theo chi phí đơn vị V[i] / W[i]

Ý tưởng: Tính tỷ lệ giá trị trên trọng lượng V[i] / W[i] cho mỗi gói, sắp xếp theo thứ tự giảm dần và lấy tỷ lệ lớn nhất có sẵn trước cho đến khi ba lô đầy.

Đối với sự thật số phân số Biến thể này áp dụng khi gói hàng tiếp theo không thể vừa hết, hãy lấy một phần gói hàng sao cho vừa khít với dung lượng còn lại. Quy tắc bổ sung đó là điều khiến Greedy Three được chứng minh là tối ưu trong bài toán Fractional Knapsack.

Các bước của thuật toán

Đối với biến thể nhánh và cận 0/1, danh sách chi phí đơn vị đã được sắp xếp sẽ điều khiển cây tìm kiếm:

• Bước 1: Nút gốc biểu thị một cái ba lô rỗng. Tổng giá trị = 0. Giới hạn trên = M × chi phí đơn vị tối đa.
• Bước 2: Phân nhánh gốc dựa trên số lượng bản sao của gói có tỷ lệ lớn nhất có thể chứa được. Với mỗi nhánh con, tính toán lại TotalValue, dung lượng còn lại M và UpperBound.
• Bước 3: Hãy mở rộng nhánh con có UpperBound lớn nhất trước, với hy vọng nhanh chóng tìm ra một giải pháp tối ưu.
• Bước 4: Loại bỏ bất kỳ nút nào có UpperBound không tốt hơn giải pháp hoàn chỉnh tốt nhất hiện tại.
• Bước 5: Khi mọi nút đều được mở rộng hoặc cắt tỉa, giải pháp hoàn chỉnh tốt nhất hiện tại sẽ đạt trạng thái tối ưu.

Mã giả cho thuật toán tham lam Fractional Knapsack thuần túy:

Fractional Knapsack (Array W, Array V, int M)
1. for i <- 1 to size(V)
2.     cost[i] <- V[i] / W[i]
3. Sort-Descending(cost)
4. total <- 0
5. i <- 1
6. while (i <= size(V) and M > 0)
7.     if W[i] <= M
8.         M <- M - W[i]
9.         total <- total + V[i]
10.        i <- i + 1
11.    else
12.        total <- total + V[i] * (M / W[i])
13.        M <- 0

Độ phức tạp của thuật toán:

• Sử dụng thuật toán sắp xếp đơn giản (chọn hoặc nổi bọt): O(n²).
• Sử dụng thuật toán sắp xếp nhanh hoặc sắp xếp trộn: Độ phức tạp O(n log n), chủ yếu do bước sắp xếp.

Java Code dành cho Ba kẻ tham lam

Xác định KnapsackPackage Lớp theo trọng lượng, giá trị và chi phí phát sinh (tỷ lệ V/W được sử dụng để phân loại):

public class KnapsackPackage {

    private double weight;
    private double value;
    private Double cost;

    public KnapsackPackage(double weight, double value) {
        super();
        this.weight = weight;
        this.value = value;
        this.cost = Double.valueOf(value / weight);
    }

    public double getWeight() { return weight; }

    public double getValue() { return value; }

    public Double getCost()  { return cost; }
}

Sau đó, hãy tạo hàm thực hiện thuật toán Greedy Three:

public void knapsackGreProc(int W[], int V[], int M, int n) {
    KnapsackPackage[] packs = new KnapsackPackage[n];
    for (int i = 0; i < n; i++) {
        packs[i] = new KnapsackPackage(W[i], V[i]);
    }

    Arrays.sort(packs, new Comparator<KnapsackPackage>() {
        @Override
        public int compare(KnapsackPackage a, KnapsackPackage b) {
            return b.getCost().compareTo(a.getCost());
        }
    });

    double remain = M;
    double result = 0d;

    for (int i = 0; i < n && remain > 0; i++) {
        if (packs[i].getWeight() <= remain) {
            remain -= packs[i].getWeight();
            result += packs[i].getValue();
            System.out.println("Pack " + i + " - Weight " + packs[i].getWeight()
                             + " - Value " + packs[i].getValue());
        } else {
            double fraction = remain / packs[i].getWeight();
            result += packs[i].getValue() * fraction;
            System.out.println("Pack " + i + " - Fraction " + fraction
                             + " - Value " + packs[i].getValue() * fraction);
            remain = 0;
        }
    }

    System.out.println("Max Value:\t" + result);
}

Hàm ba lôGreProc() trong Java

Giải thích mã:

1. Bọc mọi đầu vào vào một KnapsackPackage Vì vậy, khóa sắp xếp (tỷ lệ V/W) được tính toán trước.
2. Sắp xếp theo thứ tự giảm dần về giá cả.
3. Nếu vừa, hãy lấy nguyên cả gói.
4. Lấy một phần nhỏ của gói tiếp theo để lấp đầy chỗ trống còn lại.
5. Dừng lại ngay khi dung lượng còn lại bằng không.

Ghi chú sửa lỗi: bản gốc Java vòng lặp nâng cao i Chỉ khi nào kiện hàng không vừa, dẫn đến việc cùng một kiện hàng được lấy đi nhiều lần. Phiên bản trên sẽ di chuyển một kiện hàng mỗi lần lặp và thêm bước lấp đầy một phần, phù hợp với quy tắc Bài toán Ba lô Phân số thực sự.

Java Trình điều khiển chạy thuật toán trên một ví dụ đã được xử lý:

public void run() {
    int W[] = new int[]{15, 10, 2, 4};
    int V[] = new int[]{30, 25, 2, 6};
    int M = 37;
    int n = V.length;
    knapsackGreProc(W, V, M, n);
}

Python3 Code dành cho Ba kẻ tham lam

Trước tiên hãy định nghĩa KnapsackPackage lớp học. Các __lt__ Phương pháp này cho phép sắp xếp trực tiếp theo chi phí:

class KnapsackPackage(object):
    """Knapsack Package Data Class"""

    def __init__(self, weight, value):
        self.weight = weight
        self.value  = value
        self.cost   = value / weight

    def __lt__(self, other):
        return self.cost < other.cost

Sau đó, hãy triển khai thuật toán Fractional Knapsack:

class FractionalKnapsack(object):

    def knapsackGreProc(self, W, V, M, n):
        packs = [KnapsackPackage(W[i], V[i]) for i in range(n)]
        packs.sort(reverse=True)

        remain = M
        result = 0

        for i in range(n):
            if remain == 0:
                break
            if packs[i].weight <= remain:
                remain -= packs[i].weight
                result += packs[i].value
                print("Pack", i, "- Weight", packs[i].weight, "- Value", packs[i].value)
            else:
                fraction = remain / packs[i].weight
                result += packs[i].value * fraction
                print("Pack", i, "- Fraction", fraction,
                      "- Value", packs[i].value * fraction)
                remain = 0

        print("Max Value:", result)

Hàm ba lôGreProc() trong Python

Ghi chú sửa lỗi: bản gốc Python lớp được định nghĩa là trống __init__ không có thân thể, điều này làm tăng lên IndentationErrorPhiên bản trên đã loại bỏ hàm tạo rỗng vì nó không cần thiết.

Trình điều khiển chạy thuật toán trên ví dụ đầu tiên:

if __name__ == "__main__":
    W = [15, 10, 2, 4]
    V = [30, 25, 2, 6]
    M = 37
    n = 4

    proc = FractionalKnapsack()
    proc.knapsackGreProc(W, V, M, n)

C# Code dành cho Ba kẻ tham lam

Xác định KnapsackPackage lớp học:

using System;

namespace KnapsackProblem
{
    public class KnapsackPackage
    {
        private double weight;
        private double value;
        private double cost;

        public KnapsackPackage(double weight, double value)
        {
            this.weight = weight;
            this.value  = value;
            this.cost   = value / weight;
        }

        public double Weight { get { return weight; } }
        public double Value  { get { return value; } }
        public double Cost   { get { return cost; } }
    }
}

Triển khai thuật toán Greedy Three với bước điền dữ liệu phân số:

public void KnapsackGreProc(int[] W, int[] V, int M, int n)
{
    KnapsackPackage[] packs = new KnapsackPackage[n];
    for (int k = 0; k < n; k++)
        packs[k] = new KnapsackPackage(W[k], V[k]);

    Array.Sort<KnapsackPackage>(packs,
        (a, b) => b.Cost.CompareTo(a.Cost));

    double remain = M;
    double result = 0d;

    for (int i = 0; i < n && remain > 0; i++)
    {
        if (packs[i].Weight <= remain)
        {
            remain -= packs[i].Weight;
            result += packs[i].Value;
            Console.WriteLine("Pack " + i + " - Weight " + packs[i].Weight
                            + " - Value " + packs[i].Value);
        }
        else
        {
            double fraction = remain / packs[i].Weight;
            result += packs[i].Value * fraction;
            Console.WriteLine("Pack " + i + " - Fraction " + fraction
                            + " - Value " + packs[i].Value * fraction);
            remain = 0;
        }
    }

    Console.WriteLine("Max Value:\t" + result);
}

Hàm KnapsackGreProc() trong C#

Ví dụ phản chứng: Chiến thuật "Ba lá bài tham lam" trên bài "Ba lô 0/1".

Chiến thuật Tham Lam Ba là tối ưu cho biến thể Phân số, nhưng trên bài toán Cái túi 0/1 (nơi các vật phẩm không thể chia nhỏ) thì chiến thuật này có thể bị đánh bại. Ví dụ phản chứng:

• Tham số: n = 3, M = 10.
• Gói hàng: {i = 1; W = 7; V = 9; giá thành = 9/7}, {i = 2; W = 6; V = 6; giá thành = 1}, {i = 3; W = 4; V = 4; giá thành = 1}.
• Chiến thuật tham lam Three chọn gói 1 với tổng giá trị là 9, trong khi lựa chọn tối ưu 0/1 (gói 2, gói 3) đạt tổng giá trị là 10.

Bài học: chỉ sử dụng Greedy Three khi cho phép phân số. Đối với biến thể 0/1, hãy sử dụng Lập trình năng động thay thế.

Ứng dụng của bài toán ba lô phân đoạn

• Xếp dỡ hàng hóa, trong đó hàng hóa dạng lỏng, dạng bột hoặc dạng rời có thể được phân loại theo trọng lượng.
• Phân bổ danh mục đầu tư vào các lựa chọn đầu tư chấp nhận tài trợ một phần.
• Chia sẻ băng thông đám mây, nơi các luồng dữ liệu có thể chỉ tiêu thụ một phần nhỏ của đường truyền.
• Lập lịch CPU theo mô hình phân bổ thời gian dùng chung với khối lượng công việc có thể chia nhỏ.
• Phân bổ tài nguyên AI trong đó một tác vụ huấn luyện có thể chỉ sử dụng một phần nhỏ của GPU.

Câu Hỏi Thường Gặp