Bài toán Cái túi (Knapsack Problem) là một trong những bài toán kinh điển và nền tảng nhất trong lĩnh vực Khoa học Máy tính, đặc biệt là trong mảng Tối ưu hóa Tổ hợp (Combinatorial Optimization). Nó xuất hiện trong vô số ứng dụng thực tế, từ quản lý tài nguyên, tối ưu hóa danh mục đầu tư tài chính, đến lập kế hoạch vận chuyển.
Bạn xem thêm:
- 7 Sai Lầm Chí Mạng Khi Tự Học Python – Đừng Làm Những Điều Này
- Hướng Dẫn Cài Đặt Python và PyCharm Chi Tiết: Tránh 5 Lỗi Sai Người Mới Hay Gặp
- 50 Bài Tập Python Từ Dễ Đến Khó – Rèn Tư Duy Thuật Toán
Trong hướng dẫn này, chúng ta sẽ tập trung vào biến thể phổ biến nhất: Bài toán Knapsack 0/1. Chúng ta sẽ phân tích bản chất của vấn đề, khám phá lý do tại sao Quy hoạch động (Dynamic Programming) là công cụ lý tưởng để giải quyết nó, và triển khai một giải pháp Python mạnh mẽ, bao gồm cả các kỹ thuật tối ưu hóa không gian bộ nhớ nâng cao.
1. Phân tích Chuyên sâu Bài toán
Bài toán Knapsack 0/1 được phát biểu như sau: Cho một tập hợp các vật phẩm, mỗi vật phẩm có một trọng lượng (weight) và một giá trị (value) xác định. Chúng ta có một cái túi với sức chứa trọng lượng tối đa (Capacity). Mục tiêu là xác định tập hợp con các vật phẩm để đưa vào túi sao cho tổng giá trị là lớn nhất, mà không vượt quá sức chứa tối đa.
Điểm mấu chốt của biến thể “0/1” là chúng ta chỉ có hai lựa chọn cho mỗi vật phẩm: hoặc lấy toàn bộ nó (1), hoặc không lấy nó (0). Chúng ta không thể lấy một phần của vật phẩm.
1.1. Phân loại Bài toán
Đây là một bài toán Tối ưu hóa Tổ hợp. Do tính chất lựa chọn rời rạc (0 hoặc 1) và mục tiêu tối đa hóa, nó không thể giải quyết hiệu quả bằng các phương pháp Tham lam (Greedy). Thuật toán Tham lam thất bại vì việc lựa chọn vật phẩm tối ưu cục bộ (ví dụ: vật phẩm có tỷ lệ giá trị/trọng lượng cao nhất) không đảm bảo đạt được tối ưu toàn cục.
Bài toán này thể hiện rõ các đặc điểm cho phép áp dụng Quy hoạch động (Dynamic Programming), cụ thể là Cấu trúc con tối ưu và Các bài toán con trùng lặp.
1.2. Phân tích Input/Output
- Input:
N: Số lượng vật phẩm.W(Capacity): Sức chứa tối đa của túi (số nguyên dương).weights[]: Mảng chứa trọng lượng của từng vật phẩm.values[]: Mảng chứa giá trị của từng vật phẩm.
- Output:
- Tổng giá trị tối đa có thể đạt được.
1.3. Phân tích Ràng buộc (Constraints)
Ràng buộc của bài toán quyết định trực tiếp thuật toán khả thi.
- Ràng buộc về N (Số lượng vật phẩm):
- Nếu N rất nhỏ (N <= 20), không gian tìm kiếm là O(2^N). Phương pháp Vét cạn (Brute Force) là khả thi (khoảng 1 triệu phép tính).
- Nếu N lớn hơn (N <= 1000), O(2^N) là hoàn toàn không khả thi.
- Ràng buộc về W (Sức chứa):
- Giải pháp Quy hoạch động tiêu chuẩn có độ phức tạp thời gian là O(N*W).
- Nếu cả N và W đều ở mức trung bình (ví dụ: N <= 1000, W <= 1000), O(N*W) là rất nhanh.
- Nếu W rất lớn (ví dụ: W <= 10^9), giải pháp O(N*W) sẽ thất bại cả về thời gian lẫn bộ nhớ.
Chúng ta giả định các ràng buộc tiêu chuẩn cho phép sử dụng giải pháp O(N*W).
1.4. Trường hợp biên (Edge Cases)
- Túi không có sức chứa (W = 0): Giá trị tối đa luôn là 0.
- Không có vật phẩm nào (N = 0): Giá trị tối đa luôn là 0.
- Tất cả vật phẩm đều nặng hơn sức chứa: Thuật toán phải xử lý chính xác và trả về 0.
- Sức chứa đủ lớn để chứa tất cả: Kết quả là tổng giá trị của tất cả các vật phẩm.
2. Nền tảng Lý thuyết và Công cụ Python
Để giải quyết bài toán Knapsack 0/1 một cách hiệu quả, chúng ta phải dựa vào sức mạnh của Quy hoạch động (DP).
2.1. Quy hoạch động (Dynamic Programming) là gì?
Quy hoạch động là một kỹ thuật thiết kế thuật toán, sử dụng để giải quyết các bài toán bằng cách chia chúng thành các bài toán con nhỏ hơn, lưu trữ kết quả của các bài toán con này và tái sử dụng chúng khi cần thiết, thay vì tính toán lại.
Để áp dụng DP, bài toán phải thỏa mãn hai thuộc tính chính:
2.1.1. Cấu trúc con tối ưu (Optimal Substructure)
Một bài toán có cấu trúc con tối ưu nếu giải pháp tối ưu của nó có thể được xây dựng từ các giải pháp tối ưu của các bài toán con.
Trong Knapsack 0/1, quyết định tối ưu cho i vật phẩm đầu tiên được xây dựng dựa trên quyết định tối ưu cho i-1 vật phẩm đầu tiên. Nếu chúng ta biết giá trị tối ưu cho i-1 vật phẩm, chúng ta chỉ cần quyết định có nên bao gồm vật phẩm thứ i hay không để đạt được giá trị tối ưu mới.
2.1.2. Các bài toán con trùng lặp (Overlapping Subproblems)
Thuộc tính này xảy ra khi một thuật toán đệ quy giải quyết cùng một bài toán con nhiều lần.
Nếu chúng ta vẽ cây đệ quy cho Knapsack 0/1, chúng ta sẽ thấy các trạng thái (số lượng vật phẩm còn lại, sức chứa còn lại) lặp đi lặp lại ở nhiều nhánh khác nhau. Nếu không lưu trữ kết quả, chúng ta sẽ lãng phí tài nguyên để tính toán lại, dẫn đến độ phức tạp hàm mũ. DP giải quyết vấn đề này bằng cách lưu trữ kết quả vào một bảng (Tabulation) hoặc bộ nhớ đệm (Memoization).
2.2. Công cụ Python cho DP
Trong Python, chúng ta có các công cụ tuyệt vời để triển khai DP.
- List (Mảng): Đối với phương pháp Tabulation (Bottom-up), chúng ta thường sử dụng các danh sách lồng nhau (nested lists) để tạo ra bảng DP 2D. Ví dụ:
dp = [[0 for _ in range(W + 1)] for _ in range(N + 1)]. functools.lru_cache: Đối với phương pháp Memoization (Top-down), đây là một decorator mạnh mẽ để tự động hóa quá trình lưu trữ kết quả của hàm đệ quy.
Trong bài viết này, chúng ta sẽ tập trung vào phương pháp Tabulation (Bottom-up) vì nó thường hiệu quả hơn về mặt hiệu suất trong Python (tránh được chi phí gọi hàm đệ quy) và là nền tảng để hiểu kỹ thuật tối ưu hóa không gian.
3. Phát triển Tư duy Thuật toán
Hãy đi từ cách tiếp cận đơn giản nhất đến giải pháp tối ưu.
3.1. Hướng tiếp cận Vét cạn (Brute Force / Naive Recursion)
Ý tưởng cơ bản nhất là thử tất cả các khả năng. Đối với mỗi vật phẩm, chúng ta có hai lựa chọn: bao gồm hoặc loại trừ. Chúng ta có thể mô hình hóa điều này bằng một hàm đệ quy.
def naive_knapsack(i: int, current_capacity: int, weights: list[int], values: list[int]) -> int:
# Base Case: Hết vật phẩm (xét từ cuối về đầu) hoặc hết sức chứa
if i < 0 or current_capacity == 0:
return 0
# Nếu vật phẩm hiện tại quá nặng
if weights[i] > current_capacity:
return naive_knapsack(i - 1, current_capacity, weights, values)
# Trả về giá trị lớn nhất của hai trường hợp:
# 1. Bao gồm vật phẩm i
include = values[i] + naive_knapsack(i - 1, current_capacity - weights[i], weights, values)
# 2. Loại trừ vật phẩm i
exclude = naive_knapsack(i - 1, current_capacity, weights, values)
return max(include, exclude)
Phân tích Brute Force:
- Độ phức tạp thời gian: O(2^N). Cây đệ quy có độ sâu N và phân nhánh 2 tại mỗi bước.
- Lý do không hiệu quả: Như đã phân tích, nó tính toán lại các bài toán con trùng lặp rất nhiều lần. Với N > 20, thuật toán này không khả thi.
3.2. Tối ưu hóa và Hướng tiếp cận Hiệu quả (Quy hoạch động – Bottom-Up)
Nút thắt cổ chai là việc tính toán lặp lại. Chúng ta sẽ sử dụng DP Bottom-Up (Tabulation) để lưu trữ và tái sử dụng kết quả.
3.2.1. Xác định Trạng thái DP (State Definition)
Đây là bước quan trọng nhất. Chúng ta cần định nghĩa một trạng thái có thể nắm bắt được tiến trình của thuật toán. Có hai tham số thay đổi: số lượng vật phẩm đang xét và sức chứa khả dụng.
Gọi DP[i][w] là giá trị tối đa có thể đạt được khi chỉ xem xét i vật phẩm đầu tiên (từ 1 đến i) và với sức chứa tối đa của túi là w.
Mục tiêu cuối cùng của chúng ta là tìm DP[N][W].
3.2.2. Xác định Công thức Truy hồi (State Transition Formula)
Bây giờ chúng ta cần tìm mối quan hệ giữa DP[i][w] và các trạng thái trước đó. Khi xem xét vật phẩm thứ i (có trọng lượng wt = weights[i-1] và giá trị val = values[i-1], lưu ý chỉ số mảng bắt đầu từ 0), chúng ta có hai lựa chọn:
Lựa chọn 1: Không bao gồm vật phẩm thứ i.
Giá trị tối đa chính là giá trị chúng ta đã đạt được với i-1 vật phẩm trước đó, với cùng sức chứa w.
Giá trị = DP[i-1][w]
Lựa chọn 2: Bao gồm vật phẩm thứ i.
Điều này chỉ khả thi nếu wt <= w.
Giá trị = val + Giá trị tối đa từ i-1 vật phẩm đầu tiên với sức chứa còn lại (w – wt).
Giá trị = val + DP[i-1][w – wt]
DP[i][w] sẽ là giá trị lớn nhất giữa hai lựa chọn.
Công thức truy hồi hoàn chỉnh:
Nếu weights[i-1] > w:
DP[i][w] = DP[i-1][w] # Không thể bao gồm
Ngược lại:
DP[i][w] = max(
DP[i-1][w], # Không bao gồm
values[i-1] + DP[i-1][w - weights[i-1]] # Bao gồm
)
3.2.3. Điều kiện cơ sở và Thứ tự tính toán
- Điều kiện cơ sở:
DP[0][w] = 0(0 vật phẩm) vàDP[i][0] = 0(0 sức chứa). - Thứ tự tính toán: Vì
DP[i][w]phụ thuộc vàoDP[i-1][...], chúng ta phải tính toán theo thứ tự tăng dần củai(từ 1 đến N) và tăng dần củaw(từ 1 đến W).
Phân tích Độ phức tạp:
- Thời gian (Time Complexity): O(N*W).
- Không gian (Space Complexity): O(N*W).
4. Minh họa Thuật toán Tối ưu (Algorithm Walkthrough)
Hãy cùng xem thuật toán DP hoạt động như thế nào qua một ví dụ cụ thể.
Input:
- W = 7 (Sức chứa tối đa)
- N = 4 (Số vật phẩm)
- Items (Weight, Value):
- A: (1, 1)
- B: (3, 4)
- C: (4, 5)
- D: (5, 7)
Chúng ta khởi tạo bảng DP kích thước (4+1) x (7+1).
Khởi tạo (Hàng 0 và Cột 0):
| i/w | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1(A) | 0 | |||||||
| 2(B) | 0 | |||||||
| 3(C) | 0 | |||||||
| 4(D) | 0 |
Bước 1: Xét vật phẩm A (w=1, v=1)
DP[1][1]: w=1. Lấy A (1 + DP[0][0] = 1) hoặc không lấy (DP[0][1] = 0). Max = 1.DP[1][w](w=2 đến 7): Tương tự, giá trị là 1.
| i/w | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1(A) | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
Bước 2: Xét vật phẩm B (w=3, v=4)
DP[2][1],DP[2][2]: Trọng lượng B (3) lớn hơn w.DP[2][w] = DP[1][w] = 1.DP[2][3]: w=3.- Không lấy B:
DP[1][3] = 1. - Lấy B:
4 + DP[1][3-3] = 4 + 0 = 4. Max = 4.
- Không lấy B:
DP[2][4]: w=4.- Không lấy B:
DP[1][4] = 1. - Lấy B:
4 + DP[1][4-3] = 4 + DP[1][1] = 4 + 1 = 5. Max = 5.
- Không lấy B:
- w=5 đến 7: Tương tự, Max = 5.
| i/w | … | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 1(A) | … | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 2(B) | … | 1 | 1 | 4 | 5 | 5 | 5 | 5 |
Bước 3: Xét vật phẩm C (w=4, v=5)
- w=1 đến 3: Không thể lấy C. Copy hàng trên.
DP[3][4]: w=4.- Không lấy C:
DP[2][4] = 5. - Lấy C:
5 + DP[2][4-4] = 5 + 0 = 5. Max = 5.
- Không lấy C:
DP[3][5]: w=5.- Không lấy C:
DP[2][5] = 5. - Lấy C:
5 + DP[2][5-4] = 5 + DP[2][1] = 5 + 1 = 6. Max = 6.
- Không lấy C:
DP[3][7]: w=7.- Không lấy C:
DP[2][7] = 5. - Lấy C:
5 + DP[2][7-4] = 5 + DP[2][3] = 5 + 4 = 9. Max = 9.
- Không lấy C:
| i/w | … | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 2(B) | … | 1 | 1 | 4 | 5 | 5 | 5 | 5 |
| 3(C) | … | 1 | 1 | 4 | 5 | 6 | 6 | 9 |
Bước 4: Xét vật phẩm D (w=5, v=7)
- w=1 đến 4: Không thể lấy D. Copy hàng trên.
DP[4][5]: w=5.- Không lấy D:
DP[3][5] = 6. - Lấy D:
7 + DP[3][5-5] = 7 + 0 = 7. Max = 7.
- Không lấy D:
DP[4][7]: w=7.- Không lấy D:
DP[3][7] = 9. - Lấy D:
7 + DP[3][7-5] = 7 + DP[3][2] = 7 + 1 = 8. Max = 9.
- Không lấy D:
Kết quả cuối cùng: DP[4][7] = 9.
5. Phân tích So sánh và Các Hướng Tiếp cận Khác
Việc hiểu các hướng tiếp cận thay thế và các kỹ thuật tối ưu hóa nâng cao là rất quan trọng đối với một lập trình viên chuyên nghiệp.
5.1. DP Top-Down (Memoization) vs Bottom-Up (Tabulation)
Chúng ta đã triển khai phương pháp Bottom-Up. Phương pháp Top-Down sử dụng đệ quy có nhớ.
from functools import lru_cache
def knapsack_top_down(W: int, weights: list[int], values: list[int]) -> int:
N = len(weights)
@lru_cache(maxsize=None)
def dp(i: int, current_w: int) -> int:
if i < 0:
return 0
exclude = dp(i - 1, current_w)
include = 0
if weights[i] <= current_w:
include = values[i] + dp(i - 1, current_w - weights[i])
return max(include, exclude)
return dp(N - 1, W)
So sánh:
- Hiệu suất: Cả hai đều là O(N*W). Tuy nhiên, Bottom-Up thường nhanh hơn một chút trong Python vì nó tránh được chi phí gọi hàm đệ quy và không gặp phải giới hạn độ sâu đệ quy.
- Triển khai: Top-Down thường trực quan hơn và dễ dàng triển khai với
@lru_cache. - Tính toán trạng thái: Top-Down chỉ tính toán các trạng thái cần thiết. Bottom-Up tính toán toàn bộ bảng. Trong Knapsack 0/1, sự khác biệt này không đáng kể.
5.2. Tối ưu hóa Không gian (Space Optimization) – Kỹ thuật nâng cao
Giải pháp Bottom-Up chuẩn sử dụng không gian O(N*W). Tuy nhiên, nếu quan sát kỹ công thức truy hồi, DP[i][w] chỉ phụ thuộc vào hàng trước đó DP[i-1][...]. Chúng ta không cần lưu trữ toàn bộ bảng 2D.
Tối ưu hóa xuống 2 hàng (O(2W) -> O(W))
Chúng ta có thể chỉ sử dụng hai mảng 1D: prev_dp (cho hàng i-1) và current_dp (cho hàng i). Sau khi tính toán xong current_dp, chúng ta cập nhật prev_dp = current_dp cho lần lặp tiếp theo. Điều này giảm không gian xuống O(W).
Tối ưu hóa xuống 1 hàng (O(W))
Chúng ta có thể tối ưu hóa hơn nữa chỉ bằng một mảng 1D duy nhất DP[W+1]. Đây là một kỹ thuật tinh tế và mạnh mẽ.
Ý tưởng là sử dụng một mảng DP[w] đại diện cho giá trị tối đa đạt được với sức chứa w.
Khi chúng ta lặp qua vật phẩm thứ i, chúng ta cần cập nhật mảng DP. Tuy nhiên, chúng ta phải cực kỳ cẩn thận về thứ tự cập nhật.
Nếu chúng ta cập nhật từ trái sang phải (w=0 đến W): Khi tính DP[w], chúng ta sử dụng DP[w - weight[i]]. Giá trị này có thể đã được cập nhật trong cùng vòng lặp i hiện tại. Điều này có nghĩa là chúng ta đang sử dụng vật phẩm thứ i nhiều hơn một lần, vi phạm quy tắc 0/1 (biến nó thành bài toán Unbounded Knapsack).
Giải pháp: Để đảm bảo rằng chúng ta đang sử dụng kết quả từ vòng lặp i-1, chúng ta phải lặp từ phải sang trái (từ W xuống 0).
# Tối ưu hóa không gian O(W)
DP = [0] * (W + 1)
for i in range(N):
# Lặp ngược từ W xuống weights[i]
for w in range(W, weights[i] - 1, -1):
DP[w] = max(DP[w], values[i] + DP[w - weights[i]])
Phân tích Trade-off:
- Ưu điểm: Giảm độ phức tạp không gian từ O(N*W) xuống O(W).
- Nhược điểm: Code khó hiểu hơn. Ngoài ra, kỹ thuật này làm mất khả năng truy vết lại các vật phẩm đã được chọn (vì chúng ta không lưu lại lịch sử các trạng thái).
5.3. Thuật toán Tham lam (Greedy Algorithm)
Một sai lầm phổ biến là cố gắng áp dụng thuật toán Tham lam cho Knapsack 0/1, ví dụ như chọn vật phẩm có tỷ lệ Giá trị/Trọng lượng cao nhất trước.
Điều này thất bại. Ví dụ: W=50. Items: A(10, 60), B(20, 100), C(30, 120).
Tỷ lệ: A=6, B=5, C=4.
Greedy chọn A và B. Tổng giá trị 160.
Giải pháp tối ưu là chọn B và C. Tổng giá trị 220.
Thuật toán Tham lam chỉ hoạt động với Fractional Knapsack.
6. Triển khai Code Python Hoàn chỉnh và Kiểm thử
Dưới đây là triển khai hoàn chỉnh của cả hai phương pháp Quy hoạch động: phiên bản tiêu chuẩn (O(N*W) không gian) để đảm bảo sự rõ ràng và phiên bản tối ưu hóa không gian (O(W) không gian) cho hiệu năng cao nhất.
import time
from typing import List
def solve_knapsack_2d(capacity: int, weights: List[int], values: List[int]) -> int:
"""Solves the 0/1 Knapsack Problem using Bottom-Up Dynamic Programming (2D Table).
This approach is clear and allows for backtracking the solution (which items were picked),
although backtracking is not implemented here.
Args:
capacity: The maximum weight capacity (W) of the knapsack.
weights: A list of weights for each item.
values: A list of values for each item.
Returns:
The maximum value that can be achieved without exceeding the capacity.
Complexity Analysis:
Time Complexity: O(N*W).
Space Complexity: O(N*W).
"""
n_items = len(weights)
# Initialize DP table: (N+1) rows x (W+1) columns
# DP[i][w] represents the maximum value using the first i items with capacity w.
dp_table = [[0 for _ in range(capacity + 1)] for _ in range(n_items + 1)]
# Build the DP table in a bottom-up manner
for i in range(1, n_items + 1):
# Get the weight and value of the current item (i-1 index for lists)
current_weight = weights[i-1]
current_value = values[i-1]
for w in range(capacity + 1):
if current_weight > w:
# Case 1: Item is too heavy. Must exclude it.
dp_table[i][w] = dp_table[i-1][w]
else:
# Case 2: Item can fit. Decide whether to include or exclude it.
# Option A: Exclude the item
exclude_value = dp_table[i-1][w]
# Option B: Include the item
include_value = current_value + dp_table[i-1][w - current_weight]
# Take the maximum
dp_table[i][w] = max(exclude_value, include_value)
# The answer is the bottom-right cell
return dp_table[n_items][capacity]
def solve_knapsack_1d_optimized(capacity: int, weights: List[int], values: List[int]) -> int:
"""Solves the 0/1 Knapsack Problem using space-optimized DP (O(W) space).
This approach uses backward iteration to reduce space complexity while maintaining
O(N*W) time complexity.
Args:
capacity: The maximum weight capacity (W) of the knapsack.
weights: A list of weights for each item.
values: A list of values for each item.
Returns:
The maximum value that can be achieved.
Complexity Analysis:
Time Complexity: O(N*W).
Space Complexity: O(W).
"""
n_items = len(weights)
# Initialize a 1D DP array
# dp[w] stores the max value for capacity w using items considered so far.
dp = [0] * (capacity + 1)
for i in range(n_items):
current_weight = weights[i]
current_value = values[i]
# CRITICAL: Iterate backwards from W down to current_weight.
# This ensures we use values from the previous iteration (i-1),
# preventing the use of the same item multiple times (maintaining 0/1 property).
for w in range(capacity, current_weight - 1, -1):
# dp[w] = max(dp[w] (exclude), current_value + dp[w - current_weight] (include))
dp[w] = max(dp[w], current_value + dp[w - current_weight])
return dp[capacity]
if __name__ == "__main__":
# Helper function for testing
def run_test(test_name: str, capacity: int, weights: List[int], values: List[int], expected: int):
print(f"--- Running Test: {test_name} ---")
# Test Standard 2D DP
result_2d = solve_knapsack_2d(capacity, weights, values)
print(f"2D DP Result: {result_2d} (Expected: {expected})")
assert result_2d == expected
# Test Optimized 1D DP
result_1d = solve_knapsack_1d_optimized(capacity, weights, values)
print(f"1D Opt Result: {result_1d} (Expected: {expected})")
assert result_1d == expected
print("-" * 30 + "\n")
# Test Case 1: Standard Example
weights1 = [10, 20, 30]
values1 = [60, 100, 120]
capacity1 = 50
run_test("Standard Example", capacity1, weights1, values1, 220)
# Test Case 2: Walkthrough Example (from Section 4)
weights2 = [1, 3, 4, 5]
values2 = [1, 4, 5, 7]
capacity2 = 7
run_test("Walkthrough Example", capacity2, weights2, values2, 9)
# Test Case 3: Edge Case - No capacity
run_test("Edge Case: Zero Capacity", 0, [10, 20], [60, 100], 0)
# Test Case 4: Edge Case - No items
run_test("Edge Case: No Items", 10, [], [], 0)
# Test Case 5: All items fit
weights5 = [1, 2, 3]
values5 = [10, 15, 40]
capacity5 = 6
run_test("All Items Fit", capacity5, weights5, values5, 65)
# Test Case 6: Requires choosing optimal subset (Greedy fails)
# W=10. Items (W, V): (6, 30) ratio 5; (3, 14) ratio 4.66; (4, 16) ratio 4; (2, 9) ratio 4.5
# Greedy by ratio: (6, 30) + (3, 14) = 44. W=9.
# Optimal: (6, 30) + (4, 16) = 46. W=10.
weights6 = [6, 3, 4, 2]
values6 = [30, 14, 16, 9]
capacity6 = 10
run_test("Greedy Fails Example", capacity6, weights6, values6, 46)
Các khóa học liên quan: