Đồ án: cuối kì môn phân tích thiết kế và giải thuật knapsack problem

Đồ án cuối kì môn Phân tích thiết kế thuật toán: Giải bài toán Knapsack (bài toán cái túi). Tìm hiểu thuật toán tối ưu và cách áp dụng vào thực tế.

• Tác giả: Nguyễn Tấn Thành
• Người hướng dẫn: Gv. Nguyễn Chí Thiện
• Trường học: Trường Đại học Tôn Đức Thắng
• Chuyên ngành: Phân tích thiết kế và giải thuật
• Đề tài: Knapsack Problem
• Loại tài liệu: Đồ án cuối kì
• Năm xuất bản: 2023
• Địa điểm: Thành phố Hồ Chí Minh

Mục lục chi tiết

• LỜI CẢM ƠN
• LỜI CAM ĐOAN
• PHẦN XÁC NHẬN VÀ ĐÁNH GIÁ CỦA GIẢNG VIÊN
• TÓM TẮT
• 1. CHƯƠNG 1: MỞ ĐẦU
• 2. CHƯƠNG 2: CÁC LOẠI BÀI TOÁN TRONG KNAPSACK
• 2.1. 0/1 Knapsack Problem
• 2.2. Fractional Knapsack Problem
• 2.3. Multiple Knapsack
• 3. CHƯƠNG 3: CÁC PHƯƠNG PHÁP GIẢI BÀI TOÁN KNAPSACK PROBLEM
• 3.1. Giải quyết bài toán cái túi bằng thuật toán trực tiếp với KapSack 0/1 (Brute-force)
• 3.2. Giải quyết bài toán cái túi bằng thuật toán tham lam cho bài toán Fractional Knapsack Problem (Greedy)
• 3.3. Giải quyết bài toán cái túi bằng thuật toán quy hoạch động
• 4. CHƯƠNG 4: XÂY DỰNG DATA VÀ HIỆN THỰC THUẬT TOÁN
• 5. CHƯƠNG 5: KẾT LUẬN VỚI CÁC THUẬT TOÁN TRÊN

Tóm tắt

I. Hướng dẫn tổng quan về đồ án giải thuật Knapsack Problem

Đồ án môn Phân tích Thiết kế và Giải thuật về Knapsack Problem là một đề tài kinh điển trong lĩnh vực khoa học máy tính và tối ưu hóa tổ hợp. Về cơ bản, bài toán cái túi (Knapsack Problem) đặt ra một tình huống lựa chọn: với một tập hợp các vật phẩm, mỗi vật có trọng lượng và giá trị riêng, làm thế nào để chọn các vật phẩm bỏ vào một chiếc túi có sức chứa giới hạn sao cho tổng giá trị thu được là lớn nhất. Đây không chỉ là một bài toán lý thuyết mà còn có ý nghĩa thực tiễn sâu sắc, mô phỏng các quyết định phân bổ tài nguyên hạn chế trong nhiều ngành công nghiệp. Mục tiêu chính của đồ án là phân tích sâu các biến thể của bài toán, từ đó hiện thực và so sánh hiệu quả của các giải thuật khác nhau. Việc giải quyết thành công Knapsack Problem đòi hỏi sự hiểu biết về các kỹ thuật như quy hoạch động, giải thuật tham lam và vét cạn. Đồ án sẽ đi từ việc xây dựng mô hình toán học, phân loại các dạng bài toán, đề xuất các phương pháp giải quyết, cho đến việc hiện thực code và đánh giá hiệu năng trên các bộ dữ liệu cụ thể. Qua đó, người học có thể nắm vững cách áp dụng lý thuyết giải thuật vào giải quyết một vấn đề tối ưu hóa thực tế, một kỹ năng quan trọng cho các kỹ sư phần mềm và nhà khoa học dữ liệu. Mô hình toán học của bài toán là nền tảng cốt lõi, giúp định hình rõ ràng mục tiêu và các ràng buộc, từ đó làm cơ sở cho việc thiết kế các thuật toán hiệu quả để tìm ra lời giải tối ưu hoặc gần tối ưu cho bài toán cái túi.

1.1. Định nghĩa bài toán cái túi và mô hình toán học cốt lõi

Bài toán Knapsack Problem, hay bài toán cái túi, được mô tả như sau: Cho một danh sách gồm n đồ vật, mỗi đồ vật thứ i có một trọng lượng (weight) wᵢ và một giá trị (value) vᵢ. Cần chọn ra một tập hợp các đồ vật để đưa vào một chiếc túi có sức chứa tối đa là Capacity. Mục tiêu là làm cho tổng giá trị của các đồ vật được chọn là lớn nhất (maximize) mà không làm cho tổng trọng lượng của chúng vượt quá sức chứa của túi. Về mặt toán học, bài toán được mô hình hóa với hàm mục tiêu là tối đa hóa tổng giá trị: ∑(xᵢ * vᵢ), trong đó xᵢ là biến quyết định cho vật phẩm thứ i. Biến này có thể nhận các giá trị khác nhau tùy thuộc vào biến thể của bài toán. Hàm ràng buộc chính là tổng trọng lượng không được vượt quá sức chứa cho phép: ∑(xᵢ * wᵢ) ≤ Capacity. Các biến xᵢ phải lớn hơn hoặc bằng 0. Đây là một bài toán tối ưu hóa tổ hợp điển hình, nơi cần tìm ra cấu hình tốt nhất từ một tập hợp lớn các khả năng.

1.2. Ví dụ thực tiễn của Knapsack Problem trong quản lý

Một ví dụ thực tế và dễ hình dung về Knapsack Problem là việc một người du lịch chuẩn bị hành lý. Người đó có một chiếc ba lô với giới hạn trọng lượng nhất định (Capacity). Họ có một danh sách các vật dụng tiềm năng (quần áo, máy ảnh, sách, sạc...) và mỗi vật dụng có một trọng lượng (weight) và một mức độ hữu ích hoặc giá trị cá nhân (value). Người du lịch phải quyết định mang theo những vật dụng nào để tối đa hóa sự tiện ích cho chuyến đi mà không làm ba lô quá nặng. Một ứng dụng khác là trong quản lý dự án, nơi một nhà quản lý có ngân sách hoặc thời gian hạn chế (Capacity) và một danh sách các nhiệm vụ tiềm năng, mỗi nhiệm vụ đòi hỏi một lượng tài nguyên (weight) và mang lại một lợi ích nhất định (value). Việc giải bài toán cái túi giúp họ chọn ra danh sách nhiệm vụ tối ưu để thực hiện.

II. Phân loại các dạng bài toán Knapsack Problem phổ biến nhất

Việc hiểu rõ các biến thể của Knapsack Problem là bước đầu tiên để lựa chọn phương pháp giải quyết phù hợp. Mỗi biến thể có những ràng buộc và đặc điểm riêng, dẫn đến các cách tiếp cận thuật toán khác nhau. Ba dạng phổ biến nhất bao gồm 0/1 Knapsack Problem, Fractional Knapsack Problem, và Multiple Knapsack Problem. Trong đó, 0/1 Knapsack là dạng cơ bản và thường gặp nhất, nơi mỗi vật phẩm chỉ có hai lựa chọn: hoặc được chọn hoàn toàn, hoặc không được chọn. Điều này có nghĩa là không thể lấy một phần của vật phẩm. Biến thể này thường được giải quyết hiệu quả bằng quy hoạch động. Ngược lại, Fractional Knapsack cho phép một mức độ linh hoạt cao hơn. Với bài toán này, người giải có thể lấy một phần của một vật phẩm. Ví dụ, nếu một vật phẩm nặng 5kg và túi còn trống 2kg, có thể lấy 2/5 vật phẩm đó. Sự linh hoạt này giúp bài toán có thể được giải quyết một cách tối ưu bằng giải thuật tham lam. Cuối cùng, Multiple Knapsack là một sự mở rộng phức tạp hơn, nơi có nhiều hơn một chiếc túi, mỗi chiếc có sức chứa riêng. Mục tiêu là phân bổ các vật phẩm vào các túi này để tối đa hóa tổng giá trị. Mỗi biến thể của bài toán cái túi đều mô phỏng những kịch bản ra quyết định khác nhau trong thực tế và đòi hỏi các chiến lược giải thuật riêng biệt.

2.1. Phân biệt bài toán 0 1 Knapsack và ràng buộc lựa chọn

Trong 0/1 Knapsack Problem, ràng buộc cốt lõi là tính không thể phân chia của các vật phẩm. Đối với mỗi vật phẩm, biến quyết định xᵢ chỉ có thể nhận một trong hai giá trị: 0 (không chọn) hoặc 1 (chọn). Không có lựa chọn trung gian. Điều này làm cho không gian tìm kiếm lời giải trở nên rời rạc. Ví dụ, nếu có một viên kim cương, không thể cắt nó ra làm đôi để bỏ vào túi. Phải quyết định lấy cả viên hoặc không lấy gì cả. Ràng buộc này làm cho bài toán trở nên khó hơn so với biến thể Fractional, và các phương pháp đơn giản như tham lam thường không đưa ra kết quả tối ưu. Thay vào đó, các kỹ thuật như quy hoạch động hoặc Brute-force (với số lượng vật phẩm nhỏ) là cần thiết để đảm bảo tìm ra lời giải chính xác.

2.2. Đặc điểm của Fractional Knapsack và tính linh hoạt

Trái ngược với 0/1 Knapsack, Fractional Knapsack Problem cho phép chọn một phần của vật phẩm. Biến quyết định xᵢ có thể nhận bất kỳ giá trị thực nào trong khoảng từ 0 đến 1 (0 ≤ xᵢ ≤ 1). Điều này tương ứng với việc lấy một tỷ lệ phần trăm của vật phẩm. Ví dụ, nếu có 10kg bột vàng và túi chỉ còn chứa được 3kg, ta có thể lấy đúng 3kg bột đó. Sự linh hoạt này làm cho bài toán trở nên đơn giản hơn đáng kể. Lời giải tối ưu có thể được tìm thấy một cách hiệu quả bằng giải thuật tham lam: luôn ưu tiên chọn các vật phẩm có tỷ lệ giá trị trên trọng lượng (value/weight) cao nhất cho đến khi túi đầy. Chiến lược này đảm bảo tối ưu vì nó luôn tối đa hóa 'giá trị trên mỗi đơn vị trọng lượng'.

2.3. Mở rộng với bài toán Multiple Knapsack MKP

Multiple Knapsack Problem (MKP) là một phiên bản tổng quát hóa của bài toán cái túi cổ điển. Thay vì chỉ có một túi, bài toán này có m túi, mỗi túi i có một sức chứa Capacityᵢ riêng. Mục tiêu là phân bổ tập hợp n vật phẩm vào m túi này sao cho tổng giá trị của các vật phẩm được chọn là lớn nhất, đồng thời không vi phạm giới hạn sức chứa của bất kỳ túi nào. Biến quyết định xᵢⱼ sẽ là biến nhị phân, cho biết vật phẩm j có được đặt vào túi i hay không. Đây là một bài toán phức tạp hơn đáng kể, thường xuất hiện trong các vấn đề về logistics, lập lịch sản xuất hoặc phân bổ tài nguyên trên nhiều dự án. Các thuật toán giải quyết MKP thường là sự mở rộng của các phương pháp dùng cho 0/1 Knapsack, kết hợp với các kỹ thuật tìm kiếm và tối ưu hóa heuristic.

III. Phương pháp Brute force giải Knapsack Ưu và nhược điểm

Phương pháp Brute-force, hay còn gọi là thuật toán vét cạn, là cách tiếp cận trực tiếp và đơn giản nhất để giải quyết bài toán 0/1 Knapsack. Ý tưởng cốt lõi của nó là thử tất cả các khả năng có thể. Với n vật phẩm, mỗi vật phẩm có hai trạng thái (chọn hoặc không chọn), tổng số tổ hợp cần xem xét sẽ là 2ⁿ. Thuật toán sẽ duyệt qua từng tổ hợp, tính tổng trọng lượng và tổng giá trị của các vật phẩm được chọn trong tổ hợp đó. Nếu tổng trọng lượng không vượt quá sức chứa của túi, nó sẽ so sánh tổng giá trị hiện tại với giá trị tốt nhất đã tìm thấy và cập nhật nếu cần. Mặc dù Brute-force đảm bảo 100% sẽ tìm ra lời giải tối ưu, nhược điểm lớn nhất của nó nằm ở độ phức tạp thời gian. Độ phức tạp O(2ⁿ) khiến thuật toán này tăng trưởng theo hàm mũ. Điều này có nghĩa là nó chỉ khả thi với số lượng vật phẩm rất nhỏ (ví dụ, n < 25). Khi số lượng vật phẩm tăng lên, thời gian tính toán sẽ trở nên không thể chấp nhận được. Ví dụ, với n=30, số tổ hợp đã vượt quá một tỷ. Do đó, dù dễ triển khai, Brute-force không phải là một giải pháp thực tế cho các bài toán Knapsack Problem có kích thước lớn trong các ứng dụng công nghiệp.

3.1. Quy trình hoạt động của thuật toán vét cạn Brute force

Quy trình của thuật toán Brute-force cho 0/1 Knapsack diễn ra theo các bước tuần tự. Đầu tiên, tạo ra tất cả 2ⁿ tổ hợp lựa chọn có thể của n vật phẩm. Mỗi tổ hợp có thể được biểu diễn bằng một chuỗi bit có độ dài n, trong đó bit thứ i là 1 nếu vật phẩm i được chọn và 0 nếu không. Tiếp theo, với mỗi tổ hợp, thuật toán thực hiện hai phép tính: tính tổng trọng lượng và tổng giá trị. Sau đó, nó kiểm tra điều kiện ràng buộc: nếu tổng trọng lượng nhỏ hơn hoặc bằng Capacity của túi, tổ hợp đó được coi là hợp lệ. Cuối cùng, trong số các tổ hợp hợp lệ, thuật toán so sánh tổng giá trị của chúng và giữ lại tổ hợp có giá trị lớn nhất làm kết quả tối ưu. Mặc dù quy trình này rất rõ ràng, việc sinh và kiểm tra toàn bộ 2ⁿ tổ hợp là một gánh nặng tính toán khổng lồ.

3.2. Phân tích độ phức tạp thời gian và không gian của Brute force

Về độ phức tạp thời gian, như đã đề cập, thuật toán Brute-force có độ phức tạp là O(2ⁿ). Điều này là do nó phải duyệt qua toàn bộ không gian lời giải, bao gồm 2ⁿ tập con khác nhau của các vật phẩm. Với mỗi tập con, cần một thời gian O(n) để tính tổng trọng lượng và giá trị. Do đó, tổng thời gian là O(n * 2ⁿ). Về độ phức tạp không gian, thuật toán này tương đối hiệu quả. Nó chỉ cần không gian để lưu trữ thông tin về các vật phẩm (trọng lượng, giá trị), và một vài biến để theo dõi tổ hợp tốt nhất hiện tại. Do đó, độ phức tạp không gian thường là O(n) để lưu các mảng đầu vào và các lựa chọn tạm thời. Tuy nhiên, sự bùng nổ về thời gian tính toán là yếu tố chính hạn chế khả năng ứng dụng của phương pháp này trong thực tế.

IV. Bí quyết giải Fractional Knapsack bằng giải thuật Tham lam

Giải thuật tham lam (Greedy Algorithm) là một chiến lược cực kỳ hiệu quả và tối ưu để giải quyết Fractional Knapsack Problem. Nguyên tắc cốt lõi của phương pháp này là đưa ra lựa chọn tốt nhất tại mỗi bước, với hy vọng rằng chuỗi các lựa chọn cục bộ tối ưu này sẽ dẫn đến một giải pháp tối ưu toàn cục. Đối với bài toán cái túi phân số, lựa chọn 'tốt nhất' tại mỗi bước được xác định bằng tỷ lệ giá trị trên trọng lượng (value/weight). Vật phẩm nào có tỷ lệ này cao nhất được coi là 'đáng giá' nhất và sẽ được ưu tiên chọn trước. Quy trình giải quyết rất đơn giản: đầu tiên, tính tỷ lệ value/weight cho tất cả các vật phẩm. Sau đó, sắp xếp các vật phẩm theo thứ tự giảm dần của tỷ lệ này. Cuối cùng, duyệt qua danh sách đã sắp xếp và thêm từng vật phẩm vào túi. Nếu một vật phẩm có thể được thêm vào toàn bộ mà không vượt quá sức chứa, ta sẽ lấy toàn bộ. Nếu không, ta chỉ lấy một phần của vật phẩm đó sao cho túi được lấp đầy. Chiến lược này đảm bảo tìm ra lời giải tối ưu cho Fractional Knapsack vì nó luôn ưu tiên sử dụng từng đơn vị trọng lượng của túi một cách hiệu quả nhất có thể. Đây là một ví dụ kinh điển nơi giải thuật tham lam hoạt động hoàn hảo.

4.1. Nguyên tắc lựa chọn của thuật toán tham lam

Nguyên tắc lựa chọn của giải thuật tham lam cho Fractional Knapsack dựa trên một heuristic đơn giản nhưng mạnh mẽ: tối đa hóa giá trị trên mỗi đơn vị trọng lượng. Thuật toán không nhìn vào bức tranh toàn cảnh mà chỉ tập trung vào quyết định tức thời. Tại mỗi bước, nó đặt câu hỏi: 'Với phần sức chứa còn lại, vật phẩm nào mang lại nhiều giá trị nhất cho mỗi kg tôi thêm vào?'. Câu trả lời luôn là vật phẩm có tỷ lệ vᵢ/wᵢ cao nhất trong số các vật phẩm còn lại. Bằng cách luôn chọn vật phẩm 'đậm đặc giá trị' nhất, thuật toán đảm bảo rằng không gian trong túi luôn được sử dụng một cách hiệu quả nhất. Chiến lược này được chứng minh là luôn đưa ra kết quả tối ưu cho Fractional Knapsack, nhưng cần lưu ý rằng nó thường thất bại với bài toán 0/1 Knapsack.

4.2. Đánh giá hiệu suất và độ phức tạp của giải thuật Greedy

Giải thuật tham lam có hiệu suất rất cao. Độ phức tạp thời gian của nó chủ yếu phụ thuộc vào bước sắp xếp các vật phẩm. Nếu sử dụng một thuật toán sắp xếp hiệu quả như Merge Sort hoặc Quick Sort, bước này sẽ mất O(NlogN) thời gian, với N là số lượng vật phẩm. Sau khi đã sắp xếp, quá trình duyệt qua danh sách để lấp đầy túi chỉ mất O(N) thời gian. Do đó, tổng độ phức tạp thời gian của thuật toán là O(NlogN). Về độ phức tạp không gian, thuật toán cần các mảng để lưu trữ trọng lượng, giá trị, tỷ lệ và kết quả, tất cả đều có kích thước O(N). So với Brute-force, đây là một cải tiến vượt bậc về hiệu suất, giúp giải quyết các bài toán Fractional Knapsack có kích thước rất lớn một cách nhanh chóng.

V. Cách tiếp cận 0 1 Knapsack bằng quy hoạch động tối ưu

Quy hoạch động (Dynamic Programming - DP) là phương pháp tiêu chuẩn và hiệu quả nhất để giải quyết bài toán 0/1 Knapsack Problem. Khác với tham lam chỉ đưa ra quyết định cục bộ, DP xây dựng lời giải tối ưu bằng cách giải quyết các bài toán con nhỏ hơn và lưu trữ kết quả của chúng để tránh tính toán lại. Ý tưởng chính là tạo ra một bảng (thường là mảng 2 chiều) để lưu giá trị lớn nhất có thể đạt được với một tập hợp con các vật phẩm và một giới hạn trọng lượng nhất định. Gọi dp[i][w] là giá trị tối đa có thể có khi xem xét i vật phẩm đầu tiên với sức chứa túi là w. Để tính dp[i][w], ta có hai lựa chọn cho vật phẩm thứ i: hoặc không đưa nó vào túi, lúc này giá trị sẽ là dp[i-1][w]; hoặc đưa nó vào túi (nếu w lớn hơn trọng lượng của nó), lúc này giá trị sẽ là vᵢ + dp[i-1][w-wᵢ]. Ta sẽ chọn phương án mang lại giá trị lớn hơn. Bằng cách điền vào bảng này từ các bài toán con nhỏ nhất, cuối cùng ta sẽ tìm được giá trị tại dp[n][Capacity], đây chính là lời giải tối ưu cho bài toán ban đầu. Phương pháp quy hoạch động đảm bảo tìm ra kết quả chính xác cho 0/1 Knapsack, biến một bài toán có độ phức tạp hàm mũ (khi dùng Brute-force) thành một bài toán có độ phức tạp đa thức.

5.1. Xây dựng công thức truy hồi cho bài toán quy hoạch động

Nền tảng của giải pháp quy hoạch động là công thức truy hồi. Gọi value[i, w] là tổng giá trị lớn nhất khi chọn từ i đồ vật đầu tiên với tổng trọng số không vượt quá w. Công thức được xây dựng dựa trên việc có chọn đồ vật thứ i hay không. Nếu không chọn đồ vật thứ i, giá trị tối ưu sẽ bằng với giá trị tối ưu khi chỉ xét i-1 đồ vật đầu tiên, tức là value[i-1, w]. Nếu chọn đồ vật thứ i (chỉ có thể khi trọng lượng của nó wᵢ ≤ w), giá trị sẽ là giá trị của chính nó vᵢ cộng với giá trị tối ưu có được từ i-1 đồ vật đầu tiên với sức chứa còn lại là w - wᵢ, tức là vᵢ + value[i-1, w - wᵢ]. Do đó, công thức truy hồi cuối cùng là: value[i, w] = max(value[i-1, w], vᵢ + value[i-1, w - wᵢ]) nếu wᵢ ≤ w, và value[i, w] = value[i-1, w] nếu wᵢ > w.

5.2. Phân tích độ phức tạp thuật toán và yêu cầu bộ nhớ

Thuật toán quy hoạch động cho 0/1 Knapsack có độ phức tạp thời gian là O(N * Capacity), trong đó N là số lượng vật phẩm và Capacity là sức chứa của túi. Điều này là do thuật toán cần phải điền vào tất cả các ô của một bảng có kích thước (N+1) x (Capacity+1). Về độ phức tạp không gian, yêu cầu bộ nhớ cũng là O(N * Capacity) để lưu trữ bảng DP này. Mặc dù hiệu quả hơn nhiều so với Brute-force, độ phức tạp của DP phụ thuộc vào giá trị của Capacity. Nếu Capacity rất lớn, thuật toán này có thể trở nên không khả thi cả về thời gian và bộ nhớ. Trong những trường hợp như vậy, nó được gọi là một thuật toán thời gian giả đa thức (pseudo-polynomial time). Tuy nhiên, đối với phần lớn các trường hợp thực tế nơi Capacity là một số nguyên hợp lý, DP là giải pháp tối ưu.

VI. So sánh hiệu năng các giải thuật Knapsack qua thực nghiệm

Kết quả thực nghiệm từ việc chạy các thuật toán Brute-force, Greedy (cho Fractional Knapsack - FKP) và Dynamic Programming (DP) trên các bộ dữ liệu khác nhau đã cung cấp những hiểu biết sâu sắc về hiệu năng và tính phù hợp của từng phương pháp. Rõ ràng, Brute-force chỉ có thể áp dụng cho các bộ dữ liệu rất nhỏ (ví dụ: 8 hoặc 15 items). Khi số lượng vật phẩm tăng lên 24 (Data1), thời gian chạy của nó trở nên rất lớn (hơn 1.3 tỷ nano giây), cho thấy sự bùng nổ tổ hợp. Ngược lại, quy hoạch động và giải thuật tham lam duy trì hiệu suất ổn định hơn nhiều. DP luôn cho ra kết quả tối ưu cho bài toán 0/1 Knapsack với thời gian chạy phụ thuộc vào cả số lượng vật phẩm và sức chứa của túi. Thuật toán Greedy, dù được thiết kế cho FKP, lại có tốc độ cực nhanh, thường chỉ mất vài triệu nano giây, do độ phức tạp thời gian O(NlogN) của nó. Một điểm đáng chú ý là giá trị tối ưu của FKP (do Greedy tìm ra) luôn lớn hơn hoặc bằng giá trị tối ưu của 0/1 Knapsack (do DP và Brute-force tìm ra), điều này là hợp lý vì FKP có không gian lời giải lớn hơn. Việc so sánh này khẳng định rằng không có một thuật toán nào là tốt nhất cho mọi tình huống; việc lựa chọn phương pháp phụ thuộc vào đặc điểm cụ thể của bài toán cái túi và các ràng buộc về tài nguyên tính toán.

6.1. Đánh giá kết quả trên các bộ dữ liệu thử nghiệm

Phân tích kết quả trên năm bộ dữ liệu cho thấy sự khác biệt rõ rệt. Với Data1 (24 items, Capacity lớn), Brute-force không khả thi, trong khi DP mất khoảng 720 triệu ns và Greedy chỉ mất 9 triệu ns. Điều này nhấn mạnh sự cần thiết của các thuật toán thông minh hơn. Với các bộ dữ liệu nhỏ hơn như Data3 (8 items), Brute-force chạy nhanh (khoảng 550 nghìn ns), tương đương với Greedy và DP, cho thấy nó vẫn hữu ích cho các bài toán quy mô nhỏ. Một quan sát quan trọng là DP và Brute-force luôn cho ra cùng một giá trị tối ưu và trọng lượng tốt nhất cho bài toán 0/1 Knapsack (ví dụ: Data2, Best Value = 1458). Trong khi đó, Greedy cho FKP luôn đạt được giá trị cao hơn (Data2, Best Value = 1461.0) bằng cách lấp đầy hoàn toàn sức chứa của túi.

6.2. Kết luận chung về ưu và nhược điểm của mỗi phương pháp

Tổng kết lại, mỗi phương pháp có vị trí riêng trong việc giải quyết Knapsack Problem. Brute-force có ưu điểm là đơn giản và đảm bảo tối ưu cho 0/1 Knapsack, nhưng nhược điểm là hiệu suất cực kỳ thấp với dữ liệu lớn. Giải thuật tham lam là lựa chọn hoàn hảo cho Fractional Knapsack nhờ hiệu suất cao (O(NlogN)) và đảm bảo tối ưu, nhưng nó không áp dụng được cho 0/1 Knapsack. Cuối cùng, Quy hoạch động là giải pháp cân bằng và mạnh mẽ nhất cho 0/1 Knapsack. Nó đảm bảo tìm ra lời giải tối ưu với độ phức tạp thời gian giả đa thức O(N*Capacity), hiệu quả hơn Brute-force rất nhiều. Tuy nhiên, nhược điểm của nó là yêu cầu bộ nhớ lớn và thời gian chạy có thể cao nếu Capacity quá lớn. Việc lựa chọn thuật toán phù hợp đòi hỏi phải phân tích kỹ lưỡng các yêu cầu và ràng buộc của bài toán cụ thể.

Trích đoạn nội dung tài liệu

MỞ ĐẦU Cụ thể, bài toán có thể được mô tả như sau:  Cho một danh sách các mục, mỗi mục có một giá trị (lợi nhuận) và một trọng lượng.  Cho trước một giới hạn về trọng lượng mà một cái ba lô (hoặc một không gian) có thể chứa.  Mục tiêu là chọn một tập hợp các mục sao cho tổng giá trị là lớn nhất, nhưng tổng trọng lượng không vượt quá giới hạn đã cho. Ví dụ thực tế: Bài toán : Mô tả: Người du lịch muốn chuẩn bị một ba lô để một chuyến du lịch ngắn hạn.

Ba lô của anh ta có giới hạn trọng lượng và anh ta muốn đảm bảo rằng anh ta mang theo những vật dụng quan trọng nhất mà không vượt quá trọng lượng tối đa của ba lô. Dữ liệu vào: 4  Danh sách các mục mà anh ta có thể mang theo (quần áo, máy ảnh, sổ tay, sách, điện thoại, sạc, .)  Mỗi mục có một trọng lượng và giá trị tương ứng (có thể là tiện ích hoặc giá trị cá nhân). Dữ liệu ra:  Giá trị lớn nhất của balo đó sẽ chứa đựng.  Và số lượng những đồ vật mà balo đó.

Mô hình toán học : Ta cần tìm số đồ vật xếp vào balo sao cho tổng giá trị là lớn nhất và và trọng lượng các đồ vật không vượt quá khả năng chịu tải của Balo. Ta có:  Capacity là khả năng trọng tải của cái balo. 5  n số đồ vật, và biểu diễn quyết định của bài toánx 1, x 2, …, x n trong đó x i ≥ 0 , i=1 ,n  valuei giá trị củavậtthứ ix i  weig hti là trọng lượng của vậtthứ ix i Hàm mục tiêu : n ∑ x i .valuei →max i=1 Hàm ràng buộc : { n ∑ x i .weighti ≤ Capacity i=1 xi ≥0 và số nguyên,i=1,…,n CHƯƠNG 2 – CÁC LOẠI BÀI TOÁN TRONG KNAPSACK 2.1 0/1 Knapsack Problem:  Trong vấn đề này, mỗi đối tượng có hai lựa chọn: chọn hoặc không chọn.  Điều này có nghĩa là bạn không thể chia nhỏ một đối tượng và đặt một phần nó vào túi, mà bạn phải quyết định chọn hoặc không chọn nó nguyên vẹn.

 Ví dụ: Nếu bạn có một chiếc ba có khả năng chịu tải 10kg và ba đối tượng với trọng lượng lần lượt là 5kg, 3kg, và 8kg, bạn phải quyết định chọn đối tượng nào và không thể chia nhỏ chúng. - Hạn chế mỗi đồ vật thuộc loại 0 và 1 (không chọn, hoặc chọn) 6 Được phát biểu như sau: n ∑ i=1 x i .valuei →max Sao cho: { n ∑ i=1 x i .weighti ≤Capacity xi=0 hoặc 1 và số nguyên,i=1 ,…,n 2.2 Fractional Knapsack Problem:  Trái ngược với 0/1 Knapsack, trong vấn đề này, bạn có thể chia nhỏ đối tượng để đặt một phần của nó vào túi.  Điều này tạo ra một mức linh hoạt lớn hơn trong việc chọn lựa, vì bạn có thể chọn một phần của đối tượng để tối ưu hóa giá trị tổng cộng.  Ví dụ: Nếu bạn có một túi chịu tải 10kg và một đối tượng có trọng lượng 5kg, bạn có thể đặt nửa đối tượng vào túi để tối ưu hóa giá trị nếu giá trị của đối tượng phụ thuộc vào trọng lượng.

Bài toán: Mỗi đồ vật có thể được chọn một phần của chúng 0 ≤ x i ≤1 Được phát biểu như sau: n ∑ x i .valuei →max i=1 Sao cho: { n ∑ x i .weight i ≤Capacity i=1 0≤  x i  ≤ 1 vàsố nguyên,i=1 ,… 7 2.3 Multiple Knapsack Bài toán Multiple Knapsack (MKP) là một phần mở rộng của Bài toán ba lô cổ điển (KP), trong đó có nhiều chiếc ba lô, mỗi chiếc có hạn chế về dung lượng riêng. Trong vấn đề tối ưu hóa này, một tập hợp các vật phẩm cần được phân bổ cho các ba lô khác nhau sao cho tổng giá trị được tối đa hóa trong khi vẫn tôn trọng giới hạn dung lượng riêng của từng ba lô. Mô tả chi tiết như sau:  Nhiều Túi: Có nhiều túi, mỗi túi có một giới hạn trọng lượng cụ thể.  Nhiều Đối Tượng: Có một danh sách các đối tượng, mỗi đối tượng có trọng lượng và giá trị riêng.

 Mục Tiêu: Mục tiêu vẫn là tối ưu hóa tổng giá trị của các đối tượng được đặt vào túi, nhưng với ràng buộc là không vượt quá trọng lượng cho mỗi túi.  Thuật toán cho Multiple Knapsack Problem thường kế thừa ý tưởng từ thuật toán cho 0/1 Knapsack, nhưng mở rộng để xử lý nhiều túi. Các phương pháp giải quyết thường sử dụng các kỹ thuật như quy hoạch động hoặc các phương pháp tìm kiếm và tối ưu hóa.  Ví dụ, nếu bạn có nhiều túi với khả năng chịu tải là 10kg, 15kg và 20kg, và một danh sách các đối tượng với trọng lượng và giá trị tương ứng, thuật toán sẽ cố gắng phân phối các đối tượng vào các túi để tối ưu hóa tổng giá trị và đồng thời không vượt quá trọng lượng cho mỗi túi.

Bài toán đi tìm lời giải cho n ∑ x ij.value j →max j=1 8 Sao cho { n ∑ x ij.weight ij≤Capacity i ,Vớii ϵ[1 ,m] j=1 x ijϵ {0,1 } ,where j ϵ [ 1,n ],i ϵ[1 ,m ] Chú thích:  n là số lượng đồ vật  m là số lượng balo  value j là giá trị vật phẩm thứ j  weight ij là trọng lượng của vật phẩm j trong balo I  Capacityi là sức chứa của ba lô i  x ij là biến nhị phân cho biết vật thứ j có được chọn để đặt vào balo thứ hay không CHƯƠNG 3 – CÁC PHƯƠNG PHÁP GIẢI BÀI TOÁN KNAPSACK PROBLEM Dữ liệu đầu vào và đầu ra của các thuật toán Input : - Các thuật toán sẽ nhận vào một danh các giá trị của đồ vật (values[]) và danh sách trọng lượng của đồ vật (weights[]) vào cùng một mảng - Nhận vào Trọng tải của balo (Capacity) 9 - Số chỉ mục của 2 mảng weights[], values[] tương ứng với thứ tự đồ vật. Ví dụ: trên hình index 0 tương ứng với vật đầu tiên với: trọng lượng 70 và giá trị 135 Output : - Trả về Kiểu Tuple tự định nghĩa lưu danh sách các đồ vật được chọn hay không(1 – 0) và trả về giá trị tốt nhất Ví dụ : 3.1 Giải quyết bài toán cái túi bằng thuật toán trực tiếp với KapSack 0/1 (Brute-force) 10  Thử tất cả các2n khả năng chọn lựa để tìm ra tập con đối tượng sao cho tổng trọng lượng không vượt quá trọng lượng tối đa cho túi và tổng giá trị là lớn nhất.  Phương pháp Brute-Force là một cách tiếp cận đơn giản nhưng không hiệu quả với bài toán Knapsack và Fractional Knapsack do nó thử tất cả các khả năng có thể của việc chọn hoặc không chọn mỗi mục, sau đó kiểm tra xem liệu nó có đáp ứng các ràng buộc hay không. Dưới đây là cách giải bài toán Fractional Knapsack bằng phương pháp Brute-Force: o Tạo tất cả các tổ hợp có thể của việc chọn hoặc không chọn mỗi đối tượng.

 Mỗi đối tượng có hai lựa chọn: chọn hoặc không chọn. Do đó, số lượng tổ hợp sẽ là2n , nơi n là số lượng đối tượng. o Kiểm tra từng tổ hợp:  Đối với mỗi tổ hợp, tính tổng giá trị và tổng trọng lượng.  Kiểm tra xem tổng trọng lượng có vượt quá dung lượng của túi không.

 Nếu không, so sánh giá trị với giá trị tối ưu tới thời điểm đó và cập nhật nếu cần. o Trả về giải pháp tối ưu  Mặc dù phương pháp Brute-Force có thể đảm bảo tìm ra giải pháp tối ưu, nhưng độ phức tạp thời gian của nó là O( 2n ¿ ,nơi n là số lượng đối tượng. 11 Đối với các bài toán có số lượng đối tượng lớn, phương pháp này trở nên không hiệu quả về mặt thời gian. Ví dụ Bài toán KnapSack 0/1 Problem với giải thuật brute-force: Tổ hợp đồ Tổng trọng lượng (w=10) Tổng giá trị (max) vật Ø 0 $0 {1} 7 $42 {2} 3 $12 {3} 4 $40 {4} 5 $25 {1,2} 7+3=10 42+12 = $54 {1,3} 7+4=11 [11>10] Không khả thi {1,4} 7+5=12 [12>10] Không khả thi {2,3} 3+4=7 12+40=$52 {2,4} 3+5=8 12+25=$37 {3,4} 4+5=9 40+25=$65 12 {1,2,3} 7+3+4=14 [14>10] Không khả thi {1,2,4} 7+3+5=15 [15>10] Không khả thi {1,3,4} 7+4+5=16 [16>10] Không khả thi {2,3,4} 3+4+5=12 [12>10] Không khả thi {1,2,3,4} 7+3+4+5=19 [19>10] Không khả thi  Vậy dễ dàng thấy: giá trị lớn balô có thể chứa là $65 với đồ vật 3 và đồ vật 4.

Số tổ hợp của n đồ vật là 2n, độ phức tạp thời gian của nó là O(2n ¿. 4 4 - PersudoCode Thuật toán BruteForce (Trọng số [1 … N], Giá trị [1 … N]  Tìm sự kết hợp vật phẩm tốt nhất có thể cho KP • Đầu vào: o Trọng số mảng chứa trọng số của tất cả các mục o Giá trị mảng chứa giá trị của tất cả các mục o Mảng A được khởi tạo bằng 0 được sử dụng để tạo chuỗi bit • Đầu ra trả về mảng với: o 2 phần tử cuối của mảng lần lượt là giá trị tốt nhất và trọng lượng của nó o Các giá trị trước đó là danh sách các đồ vật được chọn 13 - Tiếp theo sử dụng vòng for lồng nhau với vòng for đầu tiên duyệt qua 2n tổ hợp để lọc chọn tổ hợp xét giá trị 14 - Vòng while bên trong sẽ chịu trách nhiệm tạo ra tổ hợp - Vòng for tiếp theo tính toán giá trị của tổ hợp và chọn giá trị tốt nhất - Cuối cùng trả về kết quả 15 Độ phức tạp cho đoạn code: - Time Complexity Analysis [ ] n n 2 1 n 2 ∑ ∑ + ∑ =∑ ¿ ¿ ¿ i=1 j =n k+1 i=1 ¿ ( 2 n ). [1 +…+1 ] ¿ ¿ O ( 2 n∗2n ) ¿ O ( n∗2 ) n - Time Complexity Analysis  Thuật toán sử dụng mảng để lưu trữ quyết định tốt nhất, quyết định tạm thời và kết quả.  Độ phức tạp không gian của các mảng là O(n), trong đó n là số lượng mục.

 Vì độ phức tạp của thuật toán này tăng theo cấp số nhân nên nó chỉ có thể được sử dụng cho các trường hợp nhỏ của Sự cố KnapSack. Mặt khác, nó không đòi hỏi nhiều nỗ lực lập trình để triển khai. Ngoài bộ nhớ được sử dụng để lưu trữ giá trị và trọng lượng của tất cả các mục, thuật toán này yêu cầu mảng hai chiều (A[] và bestChoice[]).2 Giải quyết bài toán cái túi bằng thuật toán tham lam cho bài toán Fractional Knapsack Problem (Greedy) Cách tiếp cận bài toán: 1. Chọn mục có giá trị lớn nhất trong số các mục còn lại; điều này làm tăng giá trị của chiếc ba lô càng nhanh càng tốt.