Hướng dẫn thuật toán - Đăng - Chuyên Sơn La Online Judge

1. Phân tích bài toán bằng ngôn ngữ tự nhiên

Mục tiêu: Chọn một tập hợp các vật phẩm sao cho tổng khối lượng không vượt quá và tổng giá trị là lớn nhất.
Lựa chọn: Với mỗi vật phẩm, bạn chỉ có 2 lựa chọn:
1. Chọn vật phẩm đó (nếu túi còn đủ chỗ).
2. Không chọn vật phẩm đó.
Đặc điểm: Bạn không thể chọn một vật phẩm nhiều lần (đây gọi là bài toán Knapsack 0/1).

2. Tư duy thuật toán (Quy hoạch động)

Chúng ta sẽ xây dựng một bảng dp để lưu trữ các kết quả trung gian. Gọi dp[i][j] là giá trị lớn nhất có thể đạt được khi xét từ vật phẩm thứ đến vật phẩm thứ và tổng khối lượng của chúng không vượt quá .

Công thức truy hồi:

Khi xem xét vật phẩm thứ (có khối lượng và giá trị ) với sức chứa hiện tại là :

Trường hợp 1: Không chọn vật phẩm
- Giá trị tốt nhất vẫn giống như khi ta chỉ xét vật phẩm trước đó với cùng sức chứa .
- Giá_trị_1 = dp[i-1][j]
Trường hợp 2: Chọn vật phẩm (chỉ thực hiện được nếu )
- Giá trị sẽ bằng: (Giá trị của vật ) + (Giá trị lớn nhất có thể có của vật trước đó khi sức chứa còn lại là ).
- Giá_trị_2 = v[i] + dp[i-1][j - w_i]

=> Kết quả dp[i][j] sẽ là giá trị lớn nhất giữa Giá_trị_1 và Giá_trị_2.

3. Các bước thực hiện

Nhập dữ liệu: Đọc và danh sách các cặp .
Khởi tạo: Tạo mảng 2 chiều dp[N+1][W+1] và lấp đầy bằng số 0.
Tính toán:
- Dùng vòng lặp chạy từ đến (duyệt qua từng vật).
- Dùng vòng lặp chạy từ đến (duyệt qua từng mức sức chứa của túi).
- Áp dụng công thức truy hồi để cập nhật dp[i][j].
Kết quả: Giá trị nằm ở ô cuối cùng dp[N][W] chính là đáp án.

4. Biểu diễn bằng Pseudo-code (Mã giả)

Nhập N, W
Khai báo mảng w[N+1], v[N+1]
Khai báo mảng dp[N+1][W+1], tất cả bằng 0

Cho i chạy từ 1 đến N:
    Cho j chạy từ 0 đến W:
        // Mặc định là không chọn vật i
        dp[i][j] = dp[i-1][j]
        
        // Nếu túi còn đủ chỗ để chọn vật i
        Nếu (j >= w[i]):
            Giá_trị_mới = v[i] + dp[i-1][j - w[i]]
            dp[i][j] = lớn_nhất(dp[i][j], Giá_trị_mới)

In ra dp[N][W]

5. Ví dụ minh họa (N=3, W=8)

Vật 1 (3, 30), Vật 2 (4, 50), Vật 3 (5, 60)

Xét vật 1 (w=3, v=30): Với mọi sức chứa , dp[1][j] = 30.
Xét vật 2 (w=4, v=50):
- Nếu , ta có thể chọn vật 2 và vật 1: 50 + dp[1][7-4] = 50 + 30 = 80.
Xét vật 3 (w=5, v=60):
- Nếu , ta có thể chọn vật 3 và vật 1: 60 + dp[2][8-5] = 60 + 30 = 90.
- So sánh với việc không chọn vật 3 (giá trị là dp[2][8] = 80), ta thấy 90 lớn hơn.

Kết quả cuối cùng: 90.

6. Lưu ý quan trọng

Kiểu dữ liệu: Tổng giá trị có thể rất lớn (lên tới ), nên bạn cần dùng kiểu số nguyên 64-bit (như long long trong C++) để lưu trữ mảng dp.
Tối ưu bộ nhớ: Bạn có thể nhận thấy dp[i] chỉ phụ thuộc vào dp[i-1]. Vì vậy, ta có thể tối ưu mảng 2 chiều thành mảng 1 chiều dp[W+1] để tiết kiệm bộ nhớ (khi đó vòng lặp cần chạy ngược từ về ).
Độ phức tạp: Thời gian chạy là , với và , tổng cộng là phép tính, hoàn toàn nằm trong giới hạn cho phép.