DAA - 0-1 Knapsack

Trong hướng dẫn này, trước đó chúng ta đã thảo luận về vấn đề Fractional Knapsack bằng cách sử dụng cách tiếp cận Tham lam. Chúng tôi đã chỉ ra rằng cách tiếp cận Tham lam mang lại giải pháp tối ưu cho Fractional Knapsack. Tuy nhiên, chương này sẽ đề cập đến vấn đề 0-1 Knapsack và phân tích của nó.

Trong 0-1 Knapsack, các vật phẩm không thể bị phá vỡ, có nghĩa là kẻ trộm nên lấy toàn bộ hoặc nên bỏ lại. Đây là lý do đằng sau việc gọi nó là 0-1 Knapsack.

Do đó, trong trường hợp 0-1 Knapsack, giá trị của x_i có thể là một trong hai 0 hoặc là 1, trong đó các ràng buộc khác vẫn được giữ nguyên.

0-1 Knapsack không thể được giải quyết bằng cách tiếp cận Tham lam. Cách tiếp cận tham lam không đảm bảo một giải pháp tối ưu. Trong nhiều trường hợp, cách tiếp cận Tham lam có thể đưa ra giải pháp tối ưu.

Các ví dụ sau đây sẽ thiết lập tuyên bố của chúng tôi.

Ví dụ 1

Chúng ta hãy coi rằng công suất của cái túi là W = 25 và các vật phẩm như trong bảng sau.

Mục	A	B	C	D
Lợi nhuận	24	18	18	10
Cân nặng	24	10	10	7

Không tính đến lợi nhuận trên mỗi đơn vị trọng lượng (p_i/w_i), nếu chúng ta áp dụng phương pháp Tham lam để giải quyết vấn đề này, mục đầu tiên Asẽ được lựa chọn vì nó sẽ góp phần tối đa _i mẹ lợi nhuận trong số tất cả các yếu tố.

Sau khi chọn mặt hàng A, sẽ không có mục nào được chọn. Do đó, đối với nhóm mục nhất định này, tổng lợi nhuận là24. Trong khi đó, giải pháp tối ưu có thể đạt được bằng cách chọn các mục,B và C, trong đó tổng lợi nhuận là 18 + 18 = 36.

Ví dụ-2

Thay vì chọn các mục dựa trên lợi ích tổng thể, trong ví dụ này, các mục được chọn dựa trên tỷ lệ p _i / w _i . Chúng ta hãy coi rằng công suất của cái knapsack là W = 60 và các mục như trong bảng sau.

Mục	A	B	C
Giá bán	100	280	120
Cân nặng	10	40	20
Tỉ lệ	10	7	6

Sử dụng cách tiếp cận Tham lam, mục đầu tiên Ađã được chọn. Sau đó, mục tiếp theoBlà lựa chọn. Do đó, tổng lợi nhuận là100 + 280 = 380. Tuy nhiên, giải pháp tối ưu của trường hợp này có thể đạt được bằng cách chọn các mục,B và C, tổng lợi nhuận là 280 + 120 = 400.

Do đó, có thể kết luận rằng cách tiếp cận Tham lam có thể không đưa ra giải pháp tối ưu.

Để giải quyết 0-1 Knapsack, cần có phương pháp Lập trình động.

Báo cáo vấn đề

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

Phương pháp tiếp cận lập trình động

Để cho i trở thành mục được đánh số cao nhất trong một giải pháp tối ưu S cho WUSD. Sau đóS^' = S - {i} là một giải pháp tối ưu cho W - w_i đô la và giá trị của giải pháp S Là V_i cộng với giá trị của bài toán con.

Chúng ta có thể diễn đạt thực tế này trong công thức sau: c[i, w] trở thành giải pháp cho các mặt hàng 1,2, … , ivà trọng lượng mẹ _tôi tối đaw.

Thuật toán nhận các đầu vào sau

Max _i cân mẹW
Số lượng mặt hàng n
Hai chuỗi v = <v₁, v₂, …, v_n> và w = <w₁, w₂, …, w_n>

Dynamic-0-1-knapsack (v, w, n, W) 
for w = 0 to W do 
   c[0, w] = 0 
for i = 1 to n do 
   c[i, 0] = 0 
   for w = 1 to W do 
      if w_i ≤ w then 
         if v_i + c[i-1, w-w_i] then 
            c[i, w] = v_i + c[i-1, w-w_i] 
         else c[i, w] = c[i-1, w] 
      else 
         c[i, w] = c[i-1, w]

Tập hợp các mục cần lấy có thể được suy ra từ bảng, bắt đầu từ c[n, w] và truy ngược lại nơi xuất phát các giá trị tối ưu.

Nếu c [i, w] = c [i-1, w] , thì mụci không phải là một phần của giải pháp và chúng tôi tiếp tục theo dõi c[i-1, w]. Nếu không, mụci là một phần của giải pháp và chúng tôi tiếp tục theo dõi c[i-1, w-W].

Phân tích

Thuật toán này cần θ ( n , w ) lần khi bảng c có ( n + 1). ( W + 1) mục nhập, trong đó mỗi mục nhập yêu cầu θ (1) thời gian để tính toán.