Knapsack 0/1 Problem
Tags:
Hard
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Theory Data Structure And Algorithms
No headings found
Related Posts
Theory Data Structure And Algorithms
💡
Knapsack 0/1 Problem
Đây là một bài toán tối ưu hóa kinh điển trong lĩnh vực toán học tổ hợp và khoa học máy tính. Bài toán được mô tả như sau:
- Bạn có một cái túi với sức chứa tối đa là W (trọng lượng hoặc dung tích)
- Có n vật phẩm, mỗi vật phẩm i có trọng lượng wi và giá trị vi
- Mỗi vật phẩm chỉ có thể chọn hoặc không chọn (0 hoặc 1 lần), không được chia nhỏ hay lấy nhiều lần
Mục tiêu
- Chọn một tập con các vật phẩm sao cho tổng trọng lượng không vượt quá W và tổng giá trị là lớn nhất có thể
Đặc điểm của Knapsack 0/1 Problem
- Chỉ được chọn hoặc không chọn mỗi vật phẩm: Không được lấy một phần vật phẩm hoặc lấy nhiều lần một vật phẩm
- Không chia nhỏ vật phẩm: Khác với bài toán Fractional Knapsack, ở đây mỗi vật phẩm phải được lấy nguyên vẹn hoặc không lấy
- Tối ưu hóa giá trị: Mục tiêu là tối đa hóa tổng giá trị các vật phẩm được chọn mà không vượt quá sức chứa của túi
💡
Phương pháp giải
- DP: Được sử dụng phổ biến cho bài toán này, với độ phức tạp thời gian là O(nW)
- Backtrack/ Brute-force: Chỉ phù hợp khi số lượng vật phẩm nhỏ do độ phức tạp cao
- Không áp dụng tham lam (Greedy): Vì không chia nhỏ vật phẩm nên thuật toán tham lam không đảm bảo tối ưu cho bài toán 0/1
💡
Template implement with Typescript
typescripttypescript
1function knapsack01(values: number[], weights: number[], capacity: number): number {
2 const n = values.length;
3 // Tạo bảng dp với (n+1) hàng và (capacity+1) cột, khởi tạo giá trị 0
4 const dp: number[][] = Array.from({ length: n + 1 }, () => Array(capacity + 1).fill(0));
5
6 // Duyệt từng vật phẩm
7 for (let i = 1; i <= n; i++) {
8 for (let w = 0; w <= capacity; w++) {
9 if (weights[i - 1] <= w) {
10 // Chọn hoặc không chọn vật phẩm thứ i-1
11 dp[i][w] = Math.max(
12 values[i - 1] + dp[i - 1][w - weights[i - 1]],
13 dp[i - 1][w]
14 );
15 } else {
16 // Không thể chọn vật phẩm này vì quá nặng
17 dp[i][w] = dp[i - 1][w];
18 }
19 }
20 }
21
22 // Kết quả tối ưu nằm ở dp[n][capacity]
23 return dp[n][capacity];
24}
25
26// Ví dụ sử dụng:
27const values = [60, 100, 120];
28const weights = [10, 20, 30];
29const capacity = 50;
30
31console.log(knapsack01(values, weights, capacity)); // Output: 220
32