DAA - Fractional Knapsack

Thuật toán Tham lam có thể được hiểu rất rõ ràng với một bài toán nổi tiếng được gọi là bài toán Knapsack. Mặc dù vấn đề tương tự có thể được giải quyết bằng cách sử dụng các cách tiếp cận thuật toán khác, nhưng cách tiếp cận Greedy sẽ giải quyết vấn đề Fractional Knapsack một cách hợp lý trong một thời gian thích hợp. Hãy để chúng tôi thảo luận chi tiết về vấn đề Knapsack.

Vấn đề về Knapsack

Cho một tập hợp các mục, mỗi mục có trọng lượng và giá trị, hãy xác định một tập hợp con các mục để đưa vào một bộ sưu tập sao cho tổng trọng lượng nhỏ hơn hoặc bằng một giới hạn nhất định và tổng giá trị càng lớn càng tốt.

Bài toán knapsack nằm trong bài toán tối ưu hóa tổ hợp. Nó xuất hiện như một bài toán con trong nhiều mô hình toán học phức tạp hơn của các bài toán trong thế giới thực. Một cách tiếp cận chung cho các vấn đề khó khăn là xác định ràng buộc hạn chế nhất, bỏ qua những hạn chế khác, giải quyết một vấn đề khó khăn và bằng cách nào đó điều chỉnh giải pháp để thỏa mãn các hạn chế bị bỏ qua.

Các ứng dụng

Trong nhiều trường hợp phân bổ tài nguyên cùng với một số ràng buộc, vấn đề có thể được phát sinh theo cách tương tự của vấn đề Knapsack. Sau đây là một số ví dụ.

• Tìm cách ít lãng phí nhất để cắt giảm nguyên liệu thô
• tối ưu hóa danh mục đầu tư
• Cắt giảm vấn đề tồn kho

Tình huống sự cố

Một tên trộm đang cướp một cửa hàng và có thể mang theo khối lượng tối đa là Wvào ba lô của mình. Có n mặt hàng có sẵn trong cửa hàng và trọng lượng củai^th mục là w_i và lợi nhuận của nó là p_i. Kẻ trộm nên lấy những vật dụng gì?

Trong bối cảnh này, các vật phẩm nên được chọn sao cho tên trộm sẽ mang theo những vật phẩm đó mà hắn sẽ thu được lợi nhuận tối đa. Do đó, mục tiêu của kẻ trộm là tối đa hóa lợi nhuận.

Dựa trên bản chất của các mục, các vấn đề về Knapsack được phân loại thành

• Fractional Knapsack
• Knapsack

Fractional Knapsack

Trong trường hợp này, các vật phẩm có thể bị chia thành nhiều phần nhỏ hơn, do đó kẻ trộm có thể chọn các phần nhỏ của vật phẩm.

Theo báo cáo vấn đề,

• Có n các mặt hàng trong cửa hàng

• Trọng lượng của i^th mục $ w_ {i}> 0 $

• Lợi nhuận cho i^th item $ p_ {i}> 0 $ và

• Dung lượng của Knapsack là W

Trong phiên bản này của vấn đề Knapsack, các mục có thể được chia thành nhiều mảnh nhỏ hơn. Vì vậy, kẻ trộm có thể chỉ mất một phần nhỏx_i của i^th mục.

$$ 0 \ leqslant x_ {i} \ leqslant 1 $$

Các i^th mặt hàng đóng góp trọng lượng $ x_ {i} .w_ {i} $ vào tổng trọng lượng trong bao và lợi nhuận $ x_ {i} .p_ {i} $ vào tổng lợi nhuận.

Do đó, mục tiêu của thuật toán này là

$$ tối đa hóa \: \ displaystyle \ sum \ limit_ {n = 1} ^ n (x_ {i} .p _ {} i) $$

chịu sự ràng buộc,

$$ \ displaystyle \ sum \ limit_ {n = 1} ^ n (x_ {i} .w _ {} i) \ leqslant W $$

Rõ ràng là một giải pháp tối ưu phải lấp đầy chính xác cái túi, nếu không chúng ta có thể thêm một phần nhỏ của một trong những mục còn lại và tăng lợi nhuận tổng thể.

Do đó, một giải pháp tối ưu có thể đạt được bằng cách

$$ \ displaystyle \ sum \ limit_ {n = 1} ^ n (x_ {i} .w _ {} i) = W $$

Trong ngữ cảnh này, trước tiên chúng ta cần sắp xếp các mục đó theo giá trị của $ \ frac {p_ {i}} {w_ {i}} $, sao cho $ \ frac {p_ {i} +1} {w_ {i } +1} $ ≤ $ \ frac {p_ {i}} {w_ {i}} $. Đây,x là một mảng để lưu trữ phần nhỏ của các mục.

Algorithm: Greedy-Fractional-Knapsack (w[1..n], p[1..n], W) 
for i = 1 to n 
   do x[i] = 0 
weight = 0 
for i = 1 to n 
   if weight + w[i] ≤ W then  
      x[i] = 1 
      weight = weight + w[i] 
   else 
      x[i] = (W - weight) / w[i] 
      weight = W 
      break 
return x

Phân tích

Nếu các mục được cung cấp đã được sắp xếp theo thứ tự giảm dần $ \ mathbf {\ frac {p_ {i}} {w_ {i}}} $, thì thời gian thực hiện O(n); Do đó, tổng thời gian bao gồm cả việc sắp xếp là trongO(n logn).

Thí dụ

Chúng ta hãy xem xét rằng dung lượng của chiếc túi W = 60 và danh sách các mặt hàng được cung cấp được hiển thị trong bảng sau:

Mục	A	B	C	D
Lợi nhuận	280	100	120	120
Cân nặng	40	10	20	24
Tỷ lệ $ (\ frac {p_ {i}} {w_ {i}}) $	7	10	6	5

Vì các mục đã cung cấp không được sắp xếp dựa trên $ \ mathbf {\ frac {p_ {i}} {w_ {i}}} $. Sau khi phân loại, các mục được hiển thị trong bảng sau.

Mục	B	A	C	D
Lợi nhuận	100	280	120	120
Cân nặng	10	40	20	24
Tỷ lệ $ (\ frac {p_ {i}} {w_ {i}}) $	10	7	6	5

Giải pháp

Sau khi sắp xếp tất cả các mục theo $ \ frac {p_ {i}} {w_ {i}} $. Trước hếtB được chọn làm trọng lượng của Bnhỏ hơn dung lượng của cái túi. Mục tiếp theoA được chọn, vì dung lượng khả dụng của bao lớn hơn trọng lượng của A. Hiện nay,Cđược chọn làm mục tiếp theo. Tuy nhiên, không thể chọn toàn bộ mục vì dung lượng còn lại của bao nhỏ hơn trọng lượng củaC.

Do đó, một phần của C (tức là (60 - 50) / 20) được chọn.

Bây giờ, sức chứa của Knapsack bằng với các mục đã chọn. Do đó, không thể chọn mục nào nữa.

Tổng trọng lượng của các mục đã chọn là 10 + 40 + 20 * (10/20) = 60

Và tổng lợi nhuận là 100 + 280 + 120 * (10/20) = 380 + 60 = 440

Đây là giải pháp tối ưu. Chúng tôi không thể thu được nhiều lợi nhuận hơn khi chọn bất kỳ sự kết hợp khác nhau của các mục.