Ý tưởng là để triển khai thực tế rằng phương pháp Tham lam cung cấp giải pháp tốt nhất cho vấn đề Fractional Knapsack.
Để kiểm tra xem một nút cụ thể có thể cung cấp cho chúng ta giải pháp tốt hơn hay không, chúng tôi tính toán giải pháp tối ưu (thông qua nút) thực hiện phương pháp tiếp cận Tham lam. Nếu bản thân giải pháp được tính toán theo phương pháp Greedy đã hơn giải pháp tốt nhất cho đến nay, thì chúng tôi không thể có được giải pháp tốt hơn thông qua nút này.
Thuật toán hoàn chỉnh được đưa ra bên dưới -
-
Sắp xếp tất cả các mục theo thứ tự giảm dần của tỷ lệ giá trị trên một đơn vị trọng lượng để có thể tính toán giới hạn trên khi thực hiện Phương pháp tiếp cận Tham lam.
-
Khởi tạo lợi nhuận tối đa, chẳng hạn như maxProfit =0
-
Một hàng đợi trống, Q, được tạo.
-
Một nút giả của cây quyết định được tạo và chèn hoặc xếp nó vào hàng Q. Lợi nhuận và trọng lượng của nút giả bằng 0.
-
Thực hiện theo sau khi Q không bị bỏ trống hoặc trống.
-
Một mục từ Q được tạo. Hãy để mục được trích xuất là u.
-
Tính toán lợi nhuận của nút cấp tiếp theo. Nếu lợi nhuận cao hơn maxProfit, thì hãy sửa đổi maxProfit.
-
Tính giới hạn của nút cấp tiếp theo. Nếu giới hạn cao hơn maxProfit, thì hãy thêm nút cấp tiếp theo vào Q.
-
Hãy xem xét trường hợp khi nút cấp độ tiếp theo không được xử lý hoặc được coi là một phần của giải pháp và thêm một nút vào hàng đợi với cấp độ tiếp theo, nhưng trọng số và lợi nhuận mà không xử lý hoặc xem xét các nút cấp độ tiếp theo.
-
Hình ảnh minh họa dưới đây -
Đầu vào
// First thing in every pair is treated as weight of item
// and second thing is treated as value of item
Item arr1[] = {{2, 40}, {3.14, 50}, {1.98, 100}, {5, 95}, {3, 30}};
Knapsack Capacity W1 = 10
Đầu ra
The maximum possible profit = 235