DSA Vấn đề về chiếc ba lô 0/1

Vấn đề về chiếc ba lô 0/1

Bài toán ba lô 0/1 nói rằng bạn có một chiếc ba lô có giới hạn trọng lượng và bạn đang ở trong một căn phòng chứa đầy kho báu, mỗi kho báu có giá trị và trọng lượng.

Để giải quyết Vấn đề về chiếc ba lô 0/1, bạn phải tìm ra kho báu nào cần đóng gói để tối đa hóa tổng giá trị, đồng thời giữ ở mức dưới giới hạn trọng lượng của chiếc ba lô.

Hoan hô! Bạn đã tìm thấy những vật phẩm mang lại giá trị tối đa😀

1

2

3

ba lô

$ {{totalValue }}

{{ tổng trọng lượng }}/{{giới hạn}} kg

{{ Tên mục }}

$ {{ item.value }}

{{ item.trọng lượng }} kg

Bạn có thể giải quyết vấn đề về chiếc ba lô 0/1 ở trên một cách thủ công không? Tiếp tục đọc để xem các cách triển khai khác nhau giúp giải quyết Vấn đề về chiếc ba lô 0/1.

Việc giải quyết Bài toán ba lô 0/1 giúp doanh nghiệp quyết định nên tài trợ cho dự án nào trong phạm vi ngân sách, tối đa hóa lợi nhuận mà không bội chi. Nó cũng được sử dụng trong hậu cần để tối ưu hóa việc tải hàng hóa lên xe tải và máy bay, đảm bảo đưa vào các mặt hàng có giá trị nhất hoặc được ưu tiên cao nhất mà không vượt quá giới hạn trọng lượng.

Cách tiếp cận vũ phu

Sử dụng vũ lực có nghĩa là chỉ kiểm tra mọi khả năng, tìm kiếm kết quả tốt nhất. Đây thường là cách giải quyết vấn đề đơn giản nhất nhưng cũng đòi hỏi nhiều tính toán nhất.

Để giải quyết Vấn đề về chiếc ba lô 0/1 bằng cách sử dụng vũ lực có nghĩa là:

1. Tính giá trị của mọi sự kết hợp có thể có của các vật phẩm trong ba lô.
2. Vứt bỏ các tổ hợp nặng hơn giới hạn trọng lượng của ba lô.
3. Chọn sự kết hợp của các mục có tổng giá trị cao nhất.

Cách tiếp cận mạnh mẽ này đối với bài toán Knapsack 0/1 có thể được thực hiện như sau:

 def knapsack_brute_force(capacity, n):     print(f"knapsack_brute_force({capacity},{n})")     if n == 0 or capacity == 0:         return 0      elif weights[n-1] > capacity:         return knapsack_brute_force(capacity, n-1)      else:         include_item = values[n-1] + knapsack_brute_force(capacity-weights[n-1], n-1)         exclude_item = knapsack_brute_force(capacity, n-1)         return max(include_item, exclude_item) 
values = [300, 200, 400, 500]
weights = [2, 1, 5, 3]
capacity = 10
n = len(values) 
print("\nMaximum value in Knapsack =", knapsack_brute_force(capacity, n))

Chạy đoạn mã trên có nghĩa là hàm knapsack_brute_force được gọi đệ quy nhiều lần. Bạn có thể thấy điều đó từ tất cả các bản in.

Mỗi khi hàm được gọi, nó sẽ bao gồm mục hiện tại n-1 hoặc không.

Dòng 2: Câu lệnh in này hiển thị cho chúng ta mỗi lần hàm được gọi.

Dòng 3-4: Nếu chúng tôi hết mục để kiểm tra ( n==0 ) hoặc hết dung lượng ( capacity==0 ), chúng tôi không thực hiện thêm bất kỳ cuộc gọi đệ quy nào vì không thể thêm mục nào vào ba lô vào thời điểm này.

Dòng 6-7: Nếu mục hiện tại nặng hơn dung lượng ( weights[n-1] > dung lượng ), hãy quên mục hiện tại và chuyển sang mục tiếp theo.

Dòng 10-12: Nếu vật phẩm hiện tại có thể được thêm vào ba lô, hãy xem điều gì mang lại cho bạn giá trị cao nhất: thêm vật phẩm hiện tại hoặc không thêm vật phẩm hiện tại.

Chạy đoạn mã mẫu sẽ tạo một cây đệ quy trông như thế này, mỗi hộp màu xám biểu thị một lệnh gọi hàm:

Từ cây đệ quy ở trên, có thể thấy rằng ví dụ lấy vương miện, chiếc cốc và quả địa cầu, có nghĩa là không còn chỗ cho kính hiển vi (2 kg) và điều đó cho chúng ta tổng giá trị là 200+ 400+500=1100.

Chúng ta cũng có thể thấy chỉ cần lấy kính hiển vi ra sẽ cho chúng ta tổng giá trị là 300 (ô màu xám phía dưới bên phải).

Như bạn có thể thấy trong cây đệ quy ở trên và bằng cách chạy mã ví dụ, hàm này đôi khi được gọi với cùng các đối số, chẳng hạn như knapsack_brute_force(2,0) được gọi hai lần. Chúng tôi tránh điều này bằng cách sử dụng ghi nhớ .

Phương pháp ghi nhớ (từ trên xuống)

Kỹ thuật ghi nhớ lưu trữ các kết quả của lệnh gọi hàm trước đó trong một mảng, do đó các kết quả trước đó có thể được tìm nạp từ mảng đó và không cần phải tính toán lại.

Đọc thêm về ghi nhớ ở đây .

Ghi nhớ là một cách tiếp cận 'từ trên xuống' vì nó bắt đầu giải quyết vấn đề bằng cách giải quyết các vấn đề con ngày càng nhỏ hơn.

Trong ví dụ về lực lượng vũ phu ở trên, các lệnh gọi hàm tương tự chỉ xảy ra một vài lần, do đó hiệu quả của việc sử dụng tính năng ghi nhớ không quá lớn. Nhưng trong các ví dụ khác có nhiều mục để lựa chọn hơn, kỹ thuật ghi nhớ sẽ hữu ích hơn.

Sau khi cải thiện việc triển khai bạo lực bằng cách sử dụng tính năng ghi nhớ, mã bây giờ trông như thế này:

 def knapsack_memoization(capacity, n):     print(f"knapsack_memoization({n}, {capacity})")     if memo[n][capacity] is not None:         print(f"Using memo for ({n}, {capacity})")         return memo[n][capacity]          if n == 0 or capacity == 0:         result = 0     elif weights[n-1] > capacity:         result = knapsack_memoization(capacity, n-1)     else:         include_item = values[n-1] + knapsack_memoization(capacity-weights[n-1], n-1)         exclude_item = knapsack_memoization(capacity, n-1)         result = max(include_item, exclude_item)      memo[n][capacity] = result     return result 
values = [300, 200, 400, 500]
weights = [2, 1, 5, 3]
capacity = 10
n = len(values) 
memo = [[None]*(capacity + 1) for _ in range(n + 1)] 
print("\nMaximum value in Knapsack =", knapsack_memoization(capacity, n))

Các dòng được đánh dấu trong đoạn mã trên hiển thị kỹ thuật ghi nhớ được sử dụng để cải thiện việc triển khai bạo lực trước đó.

Dòng 24: Tạo một bản ghi nhớ mảng nơi lưu trữ các kết quả trước đó.

Dòng 3-5: Khi bắt đầu hàm, trước khi thực hiện bất kỳ phép tính hoặc lệnh gọi đệ quy nào, hãy kiểm tra xem kết quả đã được tìm thấy và lưu trữ trong mảng ghi nhớ chưa.

Dòng 16: Lưu kết quả để sử dụng sau.

Phương pháp lập bảng (từ dưới lên)

Một kỹ thuật khác để giải quyết vấn đề về chiếc ba lô 0/1 là sử dụng một thứ gọi là lập bảng . Cách tiếp cận này còn được gọi là cách tiếp cận lặp và là một kỹ thuật được sử dụng trong Lập trình động .

Lập bảng giải quyết vấn đề theo cách từ dưới lên bằng cách điền vào bảng các kết quả từ các bài toán con cơ bản nhất trước tiên. Các giá trị bảng tiếp theo được điền vào bằng cách sử dụng các kết quả trước đó.

Sử dụng hình ảnh động bên dưới để xem cách điền bảng theo từng ô bằng cách sử dụng các giá trị được tính toán trước đó cho đến khi đạt được kết quả cuối cùng.

Phương pháp lập bảng hoạt động bằng cách xem xét từng mục một để tăng khả năng chứa ba lô. Bằng cách này, lời giải được xây dựng bằng cách giải các bài toán con cơ bản nhất trước tiên.

Trên mỗi hàng, một vật phẩm được coi là được thêm vào ba lô để tăng sức chứa.

 def knapsack_tabulation():     n = len(values)     tab = [[0]*(capacity + 1) for y in range(n + 1)]      for i in range(1, n+1):         for w in range(1, capacity+1):             if weights[i-1] <= w:                 include_item = values[i-1] + tab[i-1][w-weights[i-1]]                 exclude_item = tab[i-1][w]                 tab[i][w] = max(include_item, exclude_item)             else:                 tab[i][w] = tab[i-1][w]          for row in tab:        print(row)     return tab[n][capacity] 
values = [300, 200, 400, 500]
weights = [2, 1, 5, 3]
capacity = 10
print("\nMaximum value in Knapsack =", knapsack_tabulation())

Dòng 7-10: Nếu trọng lượng của mặt hàng thấp hơn sức chứa thì có nghĩa là nó có thể được thêm vào. Kiểm tra xem việc thêm nó có mang lại tổng giá trị cao hơn kết quả được tính ở hàng trước đó hay không, tức là không thêm mục. Sử dụng giá trị cao nhất ( tối đa ) của hai giá trị này. Nói cách khác: Chọn lấy hoặc không lấy vật phẩm hiện tại.

Dòng 8: Dòng này có thể là dòng khó hiểu nhất. Để tìm giá trị tương ứng với việc thêm mục hiện tại, chúng ta phải sử dụng giá trị của mục hiện tại từ mảng giá trị . Nhưng ngoài ra, chúng ta phải giảm dung lượng theo trọng lượng của vật phẩm hiện tại, để xem dung lượng còn lại có thể mang lại cho chúng ta giá trị bổ sung nào không. Điều này tương tự để kiểm tra xem các mục khác có thể được thêm vào ngoài mục hiện tại hay không và thêm giá trị của các mục đó.

Dòng 12: Trường hợp mục hiện tại nặng hơn dung lượng (quá nặng) thì chỉ cần điền giá trị từ dòng trước tức là không thêm mục hiện tại.

Chạy qua thủ công

Dưới đây là danh sách giải thích về cách tính một số giá trị trong bảng. Bạn có thể nhấp vào ô bảng tương ứng trong hình động ở trên để hiểu rõ hơn khi đọc.

Kính hiển vi, công suất 1 kg: Đối với giá trị đầu tiên được tính toán, người ta kiểm tra xem kính hiển vi có thể được đặt vào túi hay không nếu giới hạn trọng lượng là 1 kg. Kính hiển vi nặng 2 kg, quá nặng nên giá trị 0 chỉ được sao chép từ ô phía trên tương ứng với việc không có đồ vật nào trong ba lô. Chỉ xét kính hiển vi cho một chiếc túi có trọng lượng giới hạn 1 kg, đồng nghĩa với việc chúng ta không thể mang theo bất kỳ vật dụng nào và phải ra về tay không với tổng giá trị là 0$.

Kính hiển vi, sức chứa 2 kg: Đối với giá trị thứ hai được tính toán, chúng tôi có thể nhét kính hiển vi vào túi với giới hạn trọng lượng là 2 kg nên chúng tôi có thể mang theo và tổng giá trị trong túi là 300 USD (giá trị của kính hiển vi). Và đối với dung tích ba lô cao hơn, chỉ xét đến kính hiển vi, có nghĩa là chúng ta có thể mang theo nó, và vì vậy tất cả các giá trị khác trong hàng đó là 300 USD.

Quả cầu, sức chứa 1 kg: Xét quả địa cầu nặng 1 kg và sức chứa ba lô là 1 kg nghĩa là chúng ta có thể mang quả địa cầu, nên giá trị là 200$. Mã tìm giá trị lớn nhất giữa việc mang quả địa cầu mang lại cho chúng ta 200 USD, và giá trị được tính toán trước đó ở mức công suất 1 kg, là 0 USD, từ ô ở trên. Trong trường hợp này, rõ ràng là chúng ta nên mang theo quả địa cầu vì đó là vật phẩm duy nhất có trọng lượng thấp như vậy, nhưng trong các trường hợp khác, giá trị được tính toán trước đó ở cùng dung lượng có thể cao hơn.

Quả cầu, sức chứa 2 kg: Ở sức nặng 2 kg, mã thấy quả cầu có thể vừa, điều này cho ta giá trị 200$, nhưng khi đó kính hiển vi không vừa. Và việc thêm kính hiển vi cho công suất 2 kg mang lại cho chúng ta giá trị là 300$, cao hơn nên việc lấy kính hiển vi (giá trị từ ô bên trên) là lựa chọn để tối đa hóa giá trị ba lô cho ô bảng này.

Quả địa cầu có sức chứa 3 kg: Xét quả địa cầu có sức chứa 3 kg nghĩa là ta có thể lấy được quả địa cầu nhưng với trọng lượng còn lại là 2 kg ta cũng có thể lấy được cả kính hiển vi. Trong ô này, việc lấy cả quả địa cầu và kính hiển vi sẽ cho chúng ta giá trị cao hơn 200+300=500 so với việc chỉ lấy kính hiển vi (như đã tính ở dòng trước), do đó cả hai mục đều được lấy và giá trị ô là 500.

Những mặt hàng nào mang lại cho chúng tôi giá trị cao nhất?

Sau khi điền vào bảng và tìm giá trị tối đa mà chiếc ba lô có thể có, không rõ chúng ta cần mang theo những món đồ nào để có được giá trị đó.

Để tìm các mục được bao gồm, chúng tôi sử dụng bảng mà chúng tôi đã tạo và bắt đầu với ô dưới cùng bên phải có giá trị cao nhất, trong trường hợp của chúng tôi là ô có giá trị 1200 trong đó.

Dưới đây là bản vẽ về cách tìm thấy các mục đi kèm bằng phương pháp từng bước:

Đây là cách các mục bao gồm được tìm thấy:

1. Giá trị dưới cùng bên phải là 1200 và ô phía trên là 900. Các giá trị khác nhau có nghĩa là bao gồm vương miện.
2. Ô tiếp theo chúng ta đến nằm ở hàng phía trên và chúng ta di chuyển sang trái bao nhiêu lần tùy theo vương miện nặng nên còn lại 3 vị trí cho ô có giá trị 700.
3. Ô chúng ta đang ở hiện có giá trị 700 và ô ở trên có giá trị 500. Các giá trị khác nhau, có nghĩa là mục trên hàng hiện tại được bao gồm: cái cốc.
4. Chiếc cốc nặng 5 kg nên ô tiếp theo chúng ta đi đến là ở hàng trên, và 5 vị trí bên trái, đến ô có giá trị 300, trên hàng có quả địa cầu được xem xét.
5. Ô ở trên có cùng giá trị 300, có nghĩa là không bao gồm quả địa cầu và ô tiếp theo chúng ta đến là ô ngay phía trên có giá trị 300 nơi kính hiển vi được xem xét.
6. Vì ô ở trên khác với ô hiện tại có giá trị 300, điều đó có nghĩa là kính hiển vi được bao gồm.
7. Ô tiếp theo chúng ta đến nằm ở dòng trên và hai vị trí ở bên trái vì kính hiển vi nặng 2 kg.
8. Chúng tôi đến ô phía trên cùng bên trái. Vì giá trị là 0 nên có nghĩa là chúng ta đã hoàn thành.

Bài toán Ba lô 0/1 của chúng ta có giá trị lớn nhất khi bao gồm những vật phẩm này: vương miện, cốc và kính hiển vi.

Các bước tương tự được thêm vào mã bên dưới để tìm các mục tạo nên giải pháp cho vấn đề Chiếc ba lô 0/1.

 def knapsack_tabulation():     n = len(values)     tab = [[0] * (capacity + 1) for _ in range(n + 1)]      for i in range(1, n + 1):         for w in range(1, capacity + 1):             if weights[i-1] <= w:                 include_item = values[i-1] + tab[i-1][w - weights[i-1]]                 exclude_item = tab[i-1][w]                 tab[i][w] = max(include_item, exclude_item)             else:                 tab[i][w] = tab[i-1][w]      for row in tab:         print(row)      items_included = []     w = capacity     for i in range(n, 0, -1):         if tab[i][w] != tab[i-1][w]:             items_included.append(i-1)             w -= weights[i-1]      print("\nItems included:", items_included)      return tab[n][capacity] 
values = [300, 200, 400, 500]
weights = [2, 1, 5, 3]
capacity = 10
print("\nMaximum value in Knapsack =", knapsack_tabulation())

Độ phức tạp thời gian

Ba cách tiếp cận để giải quyết Bài toán chiếc ba lô 0/1 diễn ra khác nhau và có độ phức tạp về thời gian khác nhau.

Phương pháp tiếp cận Brute Force: Đây là phương pháp chậm nhất trong ba phương pháp. Các khả năng được kiểm tra đệ quy, với độ phức tạp về thời gian \(O(2^n)\), trong đó \(n\) là số lượng mặt hàng tiềm năng mà chúng tôi có thể đóng gói. Điều này có nghĩa là số lượng tính toán tăng gấp đôi cho mỗi mục bổ sung cần được xem xét.

Phương pháp ghi nhớ: Lưu các tính toán bằng cách ghi nhớ các kết quả trước đó, điều này dẫn đến độ phức tạp về thời gian tốt hơn \(O(n \cdot C)\), trong đó \(n\) là số lượng mục và \(C\) là chiếc ba lô dung tích. Cách tiếp cận này hoạt động theo cách đệ quy tương tự như cách tiếp cận vũ phu.

Phương pháp lập bảng: Có độ phức tạp về thời gian tương tự như phương pháp ghi nhớ \(O(n \cdot C)\), trong đó \(n\) là số mục và \(C\) là dung lượng ba lô, nhưng mức sử dụng bộ nhớ và cách nó diễn ra dễ dự đoán hơn, điều này thường làm cho cách tiếp cận lập bảng là thuận lợi nhất.