Dưới đây, chúng ta sẽ xem xét một chương trình trong Excel VBA giải quyết một trường hợp nhỏ của vấn đề ba lô.

Định nghĩa: 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 các mục cần đưa vào một bộ sưu tập sao cho tổng giá trị càng lớn càng tốt và tổng trọng lượng nhỏ hơn một giới hạn nhất định.

Tên gọi của nó bắt nguồn từ vấn đề mà ai đó phải đối mặt, người bị bó buộc bởi một cái túi có kích thước cố định và phải lấp đầy nó bằng những thứ hữu ích nhất.

Ví dụ: 5 mục có trọng lượng, giá trị và giới hạn như đã cho.

Knapsack Problem Image

Trong Excel, vấn đề này trông như sau:

Knapsack Problem Example

  1. Đầu tiên, chúng ta khai báo năm biến kiểu Double với các tên limit, weight, value, totalWeight và MaximumValue.

Dim limit As Double, weight As Double, value As Double, totalWeight As Double, maximumValue As Double

  1. Tiếp theo, chúng ta khai báo năm biến kiểu Integer với các tên i, j, k, l, m.

Dim i, j, k, l, m As Integer

  1. Chúng tôi khởi tạo hai biến. Chúng ta khởi tạo giới hạn biến với giá trị của ô D6. Chúng tôi khởi tạo biến MaximumValue với giá trị 0.

limit = Range("D6").value

maximumValue = 0

  1. Tiếp theo, chúng tôi kiểm tra từng giải pháp khả thi. Chúng ta có thể bao gồm một mục (1) hoặc bỏ nó đi (0). Chúng ta bắt đầu 5 vòng lặp For Next. Một cho mỗi mục.

For i = 0 To 1

For j = 0 To 1

For k = 0 To 1

For l = 0 To 1

For m = 0 To 1

  1. Chúng tôi tính toán trọng lượng và giá trị của một giải pháp khả thi.

weight = 12  i + 2  j + 1  k + 1  l + 4  m

value = 4  i + 2  j + 2  k + 1  l + 10  m

  1. Chỉ khi giá trị cao hơn MaximumValue và trọng lượng thấp hơn giới hạn, chúng tôi đã tìm ra giải pháp mới tốt hơn.

If value > maximumValue And weight <= limit Then

  1. Nếu đúng, chúng tôi viết lời giải mới vào hàng 4, trọng số là TotalWeight và giá trị là MaximumValue.

Range("B4").value = i

Range("C4").value = j

Range("D4").value = k

Range("E4").value = l

Range("F4").value = m

totalWeight = weight

maximumValue = value

  1. Đừng quên đóng câu lệnh If.

End If

  1. Đừng quên đóng 5 vòng lặp For Next.

Next m

Next l

Next k

Next j

Next i

Excel VBA kiểm tra từng giải pháp khả thi theo cách này và kết quả là giải pháp tối ưu sẽ xuất hiện ở hàng 4. Hãy nhớ rằng, 1 có nghĩa là chúng tôi bao gồm một mục, 0 có nghĩa là chúng tôi bỏ nó đi.

  1. Cuối cùng, viết totalWeight và MaximumValue của giải pháp tối ưu lần lượt vào ô B6 và B8.

Range("B6").value = totalWeight

Range("B8").value = maximumValue

  1. Chạy thử chương trình.

Kết quả:

Knapsack Problem Result

Kết luận: tối ưu là bao gồm bốn mục cuối cùng với giá trị lớn nhất là 15. Giải pháp này với tổng trọng số 2 + 1 + 1 + 4 = 8 không vượt quá giới hạn của 15.

Lưu ý: bằng cách làm cho trọng số và giá trị biến đổi, bạn có thể giải quyết bất kỳ vấn đề nào về gói có kích thước này (xem tệp Excel có thể tải xuống).