Bài 27.2: Bài toán cái túi unbounded

Chào mừng bạn trở lại với loạt bài về Cấu trúc dữ liệu và Giải thuật! Sau khi đã làm quen với bài toán cái túi 0/1 kinh điển, hôm nay chúng ta sẽ khám phá một người anh em thú vị không kém: Bài toán cái túi Unbounded (Unbounded Knapsack Problem), hay còn gọi là bài toán cái túi với số lượng vật phẩm không giới hạn.

Khác với phiên bản 0/1 nơi mỗi vật phẩm bạn chỉ có thể chọn hoặc không chọn (tối đa một lần), trong bài toán Unbounded, bạn có thể cho vào túi bất kỳ số lượng nào của mỗi loại vật phẩm, miễn là tổng trọng lượng không vượt quá sức chứa của túi. Mục tiêu vẫn vậy: tối đa hóa tổng giá trị các vật phẩm được chọn.

Nghe có vẻ đơn giản hơn vì không bị giới hạn số lượng, nhưng chính điều này lại thay đổi cách chúng ta tiếp cận bài toán bằng quy hoạch động (Dynamic Programming - DP) so với bài toán 0/1.

Hãy cùng đi sâu vào chi tiết!

Bài toán Cái túi Unbounded là gì?

Phát biểu một cách hình thức, bài toán như sau:

Cho một cái túi có sức chứa tối đa là W. Cho N loại vật phẩm. Mỗi loại vật phẩm i có trọng lượng là w_i và giá trị là v_i. Bạn có thể chọn bất kỳ số lượng nào của mỗi loại vật phẩm. Tìm cách chọn các vật phẩm sao cho tổng trọng lượng của chúng không vượt quá W và tổng giá trị của chúng là lớn nhất có thể.

Ví dụ thực tế của bài toán này có thể là:

Một người bán hàng cần đóng gói một thùng hàng (túi) với trọng lượng tối đa cho phép. Anh ta có nhiều loại sản phẩm khác nhau (vật phẩm), mỗi loại có trọng lượng và giá trị riêng, và anh ta có kho không giới hạn mỗi loại sản phẩm. Anh ta muốn đóng gói sao cho giá trị thùng hàng là cao nhất.
Bài toán "đổi tiền" (Coin Change Problem) để đạt được một tổng tiền nhất định với số lượng tiền xu không giới hạn cũng là một biến thể của Unbounded Knapsack (thay vì tối đa hóa giá trị, ta thường tối thiểu hóa số lượng xu, hoặc đếm số cách).
Bài toán "cắt thanh sắt" (Rod Cutting Problem) cũng có cấu trúc tương tự.

Tại sao Quy hoạch động lại phù hợp?

Giống như bài toán 0/1, bài toán Unbounded Knapsack cũng thể hiện hai đặc điểm quan trọng mà DP yêu thích:

Cấu trúc tối ưu con (Optimal Substructure): Lời giải tối ưu cho một cái túi sức chứa W có thể được xây dựng từ lời giải tối ưu cho các cái túi sức chứa nhỏ hơn.
Bài toán con gối chồng (Overlapping Subproblems): Khi giải quyết bài toán cho sức chứa W, chúng ta sẽ liên tục cần kết quả cho các sức chứa nhỏ hơn, và những bài toán con này lặp lại nhiều lần.

Xây dựng công thức Quy hoạch động

Chúng ta sẽ sử dụng phương pháp DP "bottom-up", xây dựng lời giải từ các sức chứa nhỏ nhất đến sức chứa lớn nhất W.

Hãy định nghĩa mảng DP:

dp[w] sẽ là giá trị lớn nhất có thể đạt được khi cái túi có sức chứa chính xác là w. (Lưu ý: một số định nghĩa DP dùng sức chứa tối đa là w, nhưng với Unbounded Knapsack, định nghĩa "chính xác" thường dẫn đến công thức đơn giản hơn).

Công thức truy hồi (Recurrence Relation):

Để tính dp[w], chúng ta xét tất cả các loại vật phẩm i có trọng lượng w_i nhỏ hơn hoặc bằng w. Nếu chúng ta quyết định đặt một vật phẩm loại i vào túi khi sức chứa là w, thì phần sức chứa còn lại sẽ là w - w_i. Giá trị lớn nhất có thể đạt được với sức chứa còn lại này là dp[w - w_i]. Do đó, tổng giá trị khi thêm vật phẩm i sẽ là dp[w - w_i] + v_i.

Vì chúng ta có thể chọn bất kỳ loại vật phẩm nào cuối cùng để đạt được sức chứa w, dp[w] sẽ là giá trị lớn nhất trong tất cả các khả năng này:

dp[w] = max(dp[w], dp[w - w_i] + v_i) cho mọi vật phẩm i mà w_i <= w.

Trạng thái cơ bản (Base Case):

dp[0] = 0 (Một cái túi sức chứa 0 thì giá trị lớn nhất là 0).

Khởi tạo:

Chúng ta cần một mảng dp có kích thước W + 1, được khởi tạo với giá trị 0. dp[w] lưu trữ giá trị lớn nhất cho sức chứa w.

Thứ tự tính toán:

Đây là điểm khác biệt quan trọng so với bài toán cái túi 0/1 khi sử dụng mảng 1 chiều!

Trong 0/1 Knapsack 1D DP, chúng ta lặp qua vật phẩm trước, rồi lặp qua sức chứa từ W giảm dần về w_i. Việc lặp ngược đảm bảo mỗi vật phẩm chỉ được xét một lần cho mỗi sức chứa.

Trong Unbounded Knapsack, chúng ta lặp qua vật phẩm trước, rồi lặp qua sức chứa từ w_i tăng dần đến W. Việc lặp xuôi dp[w] = max(dp[w], dp[w - w_i] + v_i) cho phép cùng một vật phẩm i được sử dụng để tính dp[w - w_i] (tức là vật phẩm i đã được "đặt vào túi" ở bước trước với sức chứa nhỏ hơn), sau đó lại được sử dụng tiếp để tính dp[w] từ dp[w - w_i], hiệu quả là vật phẩm i được chọn nhiều lần.

Hoặc, một cách tương đương và thường được sử dụng hơn để làm rõ ý tưởng "chọn một vật phẩm cuối cùng để lấp đầy túi đến sức chứa w": chúng ta có thể lặp qua sức chứa trước, rồi lặp qua các vật phẩm.

Công thức vẫn là: dp[w] = max(dp[w], dp[w - w_i] + v_i)

Thứ tự lặp:

Lặp qua sức chứa w từ 1 đến W.
Bên trong vòng lặp sức chứa, lặp qua mọi loại vật phẩm i.
Nếu w_i <= w, cập nhật dp[w] = max(dp[w], dp[w - w_i] + v_i).

Lý do thứ tự lặp này hoạt động cho Unbounded Knapsack: Khi chúng ta tính dp[w], chúng ta xét khả năng vật phẩm i là vật phẩm cuối cùng được thêm vào để đạt được sức chứa w. Sức chứa còn lại trước khi thêm vật phẩm i là w - w_i, và giá trị lớn nhất cho sức chứa này là dp[w - w_i]. Do chúng ta lặp qua w theo thứ tự tăng dần, giá trị dp[w - w_i] đã được tính toán trước đó và nó đã xem xét khả năng sử dụng vật phẩm i (hoặc bất kỳ vật phẩm nào khác) nhiều lần để đạt được sức chứa w - w_i. Do đó, công thức dp[w] = max(dp[w], dp[w - w_i] + v_i) tự động xem xét việc sử dụng vật phẩm i nhiều lần.

Hãy xem xét thứ tự lặp thứ hai (lặp sức chứa ngoài, vật phẩm trong) trong các ví dụ code.

Ví dụ Minh họa 1

Giả sử chúng ta có các loại vật phẩm và sức chứa túi như sau:

Túi có sức chứa W = 5.
Vật phẩm 1: trọng lượng w_1 = 2, giá trị v_1 = 3.
Vật phẩm 2: trọng lượng w_2 = 3, giá trị v_2 = 4.

Chúng ta cần tính dp[0] đến dp[5]. Khởi tạo: dp = {0, 0, 0, 0, 0, 0} (kích thước 6)

Lặp qua sức chứa w từ 1 đến 5:

w = 1:
- Vật phẩm 1 (w=2): w_1 > w, không thể thêm.
- Vật phẩm 2 (w=3): w_2 > w, không thể thêm.
- dp[1] giữ nguyên là 0. dp = {0, 0, 0, 0, 0, 0}.
w = 2:
- Vật phẩm 1 (w=2): w_1 <= w. dp[2] = max(dp[2], dp[2 - 2] + 3) = max(dp[2], dp[0] + 3) = max(0, 0 + 3) = 3. dp = {0, 0, 3, 0, 0, 0}.
- Vật phẩm 2 (w=3): w_2 > w, không thể thêm.
- dp[2] là 3. dp = {0, 0, 3, 0, 0, 0}.
w = 3:
- Vật phẩm 1 (w=2): w_1 <= w. dp[3] = max(dp[3], dp[3 - 2] + 3) = max(dp[3], dp[1] + 3) = max(0, 0 + 3) = 3. dp = {0, 0, 3, 3, 0, 0}.
- Vật phẩm 2 (w=3): w_2 <= w. dp[3] = max(dp[3], dp[3 - 3] + 4) = max(3, dp[0] + 4) = max(3, 0 + 4) = 4. dp = {0, 0, 3, 4, 0, 0}.
- dp[3] là 4. dp = {0, 0, 3, 4, 0, 0}.
w = 4:
- Vật phẩm 1 (w=2): w_1 <= w. dp[4] = max(dp[4], dp[4 - 2] + 3) = max(dp[4], dp[2] + 3) = max(0, 3 + 3) = 6. dp = {0, 0, 3, 4, 6, 0}.
- Vật phẩm 2 (w=3): w_2 <= w. dp[4] = max(dp[4], dp[4 - 3] + 4) = max(6, dp[1] + 4) = max(6, 0 + 4) = 6. dp = {0, 0, 3, 4, 6, 0}.
- dp[4] là 6. dp = {0, 0, 3, 4, 6, 0}.
w = 5:
- Vật phẩm 1 (w=2): w_1 <= w. dp[5] = max(dp[5], dp[5 - 2] + 3) = max(dp[5], dp[3] + 3) = max(0, 4 + 3) = 7. dp = {0, 0, 3, 4, 6, 7}.
- Vật phẩm 2 (w=3): w_2 <= w. dp[5] = max(dp[5], dp[5 - 3] + 4) = max(7, dp[2] + 4) = max(7, 3 + 4) = 7. dp = {0, 0, 3, 4, 6, 7}.
- dp[5] là 7. dp = {0, 0, 3, 4, 6, 7}.

Kết quả cuối cùng là dp[5] = 7.

Điều này có nghĩa với sức chứa 5, giá trị lớn nhất có thể đạt được là 7. Cách kết hợp vật phẩm để đạt được giá trị này có thể là: 1 vật phẩm loại 1 (w=2, v=3) + 1 vật phẩm loại 2 (w=3, v=4) -> tổng w=5, tổng v=7.

Code Minh họa 1 (C++)

Dưới đây là code C++ triển khai giải thuật DP cho ví dụ trên:

#include <iostream>
#include <vector>
#include <algorithm>

struct Item {
    int weight;
    int value;
};

int main() {
    // Input cho Ví dụ 1
    int W = 5; // Sức chứa túi
    std::vector<Item> items = {
        {2, 3}, // Vật phẩm 1: w=2, v=3
        {3, 4}  // Vật phẩm 2: w=3, v=4
    };
    int N = items.size(); // Số loại vật phẩm

    // Mảng DP: dp[w] = giá trị lớn nhất với sức chứa w
    std::vector<int> dp(W + 1, 0);

    // Xây dựng bảng DP
    // Lặp qua từng mức sức chứa từ 1 đến W
    for (int w = 1; w <= W; ++w) {
        // Với mỗi mức sức chứa w, xét tất cả các loại vật phẩm
        for (int i = 0; i < N; ++i) {
            // Nếu vật phẩm i có thể cho vào túi (trọng lượng <= sức chứa hiện tại)
            if (items[i].weight <= w) {
                // Cập nhật dp[w]:
                // Lựa chọn 1: Không dùng vật phẩm i làm vật phẩm cuối cùng để đạt sức chứa w (giá trị là dp[w] hiện tại)
                // Lựa chọn 2: Dùng vật phẩm i làm vật phẩm cuối cùng để đạt sức chứa w
                //             Giá trị sẽ là (giá trị lớn nhất với sức chứa còn lại w - items[i].weight) + giá trị của vật phẩm i
                dp[w] = std::max(dp[w], dp[w - items[i].weight] + items[i].value);
            }
        }
    }

    // Kết quả là giá trị lớn nhất có thể đạt được với sức chứa W
    std::cout << "Gia tri lon nhat voi tui suc chua " << W << " la: " << dp[W] << std::endl;

    return 0;
}

Giải thích Code 1:

Headers: Bao gồm iostream để nhập/xuất, vector để sử dụng mảng động dp, và algorithm cho hàm std::max.
struct Item: Định nghĩa cấu trúc đơn giản để lưu trữ trọng lượng (weight) và giá trị (value) của mỗi loại vật phẩm.
Input: Khai báo sức chứa W và vector items chứa thông tin các loại vật phẩm. N là số loại vật phẩm.
Mảng DP: std::vector<int> dp(W + 1, 0); tạo ra một vector có kích thước W+1 và khởi tạo tất cả các phần tử bằng 0. dp[i] sẽ lưu trữ giá trị tối đa đạt được với sức chứa i.
Vòng lặp DP chính:
- Vòng ngoài for (int w = 1; w <= W; ++w): Duyệt qua tất cả các sức chứa từ 1 đến W. Chúng ta đang tính toán giá trị tối ưu cho từng mức sức chứa tăng dần.
- Vòng trong for (int i = 0; i < N; ++i): Với mỗi mức sức chứa w, duyệt qua tất cả các loại vật phẩm có sẵn.
Điều kiện và Cập nhật:
- if (items[i].weight <= w): Kiểm tra xem vật phẩm loại i có thể được cho vào túi khi túi có sức chứa w hay không.
- dp[w] = std::max(dp[w], dp[w - items[i].weight] + items[i].value);: Đây chính là công thức truy hồi. Nó so sánh giá trị hiện tại của dp[w] (giá trị tối ưu cho sức chứa w mà không sử dụng vật phẩm i làm vật phẩm cuối cùng trong lần cập nhật này) với giá trị đạt được bằng cách thêm vật phẩm i. Nếu thêm vật phẩm i, chúng ta cần phải tính giá trị tối ưu cho phần sức chứa còn lại là w - items[i].weight, đó chính là dp[w - items[i].weight], và cộng thêm giá trị của vật phẩm i. Hàm std::max chọn giá trị tốt nhất giữa hai khả năng này.
Kết quả: Sau khi hoàn thành các vòng lặp, dp[W] sẽ chứa giá trị lớn nhất có thể đạt được với sức chứa W.

Ví dụ Minh họa 2

Hãy thử với một tập vật phẩm và sức chứa khác:

Túi có sức chứa W = 8.
Vật phẩm 1: trọng lượng w_1 = 1, giá trị v_1 = 10.
Vật phẩm 2: trọng lượng w_2 = 3, giá trị v_2 = 30.
Vật phẩm 3: trọng lượng w_3 = 4, giá trị v_3 = 40.

Khởi tạo: dp = {0, 0, 0, 0, 0, 0, 0, 0, 0} (kích thước 9)

Lặp qua sức chứa w từ 1 đến 8:

w = 1: dp[1] = max(dp[1], dp[1-1]+10) (vật phẩm 1) = max(0, 0+10) = 10. dp={0,10,0,0,0,0,0,0,0}.
w = 2: dp[2] = max(dp[2], dp[2-1]+10) (vật phẩm 1) = max(0, dp[1]+10) = max(0, 10+10) = 20. dp={0,10,20,0,0,0,0,0,0}.
w = 3:
- Vật phẩm 1: dp[3] = max(dp[3], dp[3-1]+10) = max(0, dp[2]+10) = max(0, 20+10) = 30.
- Vật phẩm 2: dp[3] = max(30, dp[3-3]+30) = max(30, dp[0]+30) = max(30, 0+30) = 30.
- dp[3] là 30. dp={0,10,20,30,0,0,0,0,0}.
w = 4:
- Vật phẩm 1: dp[4] = max(dp[4], dp[4-1]+10) = max(0, dp[3]+10) = max(0, 30+10) = 40.
- Vật phẩm 2: dp[4] = max(40, dp[4-3]+30) = max(40, dp[1]+30) = max(40, 10+30) = 40.
- Vật phẩm 3: dp[4] = max(40, dp[4-4]+40) = max(40, dp[0]+40) = max(40, 0+40) = 40.
- dp[4] là 40. dp={0,10,20,30,40,0,0,0,0}.
w = 5:
- Vật phẩm 1: dp[5] = max(dp[5], dp[5-1]+10) = max(0, dp[4]+10) = max(0, 40+10) = 50.
- Vật phẩm 2: dp[5] = max(50, dp[5-3]+30) = max(50, dp[2]+30) = max(50, 20+30) = 50.
- Vật phẩm 3: dp[5] = max(50, dp[5-4]+40) = max(50, dp[1]+40) = max(50, 10+40) = 50.
- dp[5] là 50. dp={0,10,20,30,40,50,0,0,0}.
w = 6:
- Vật phẩm 1: dp[6] = max(dp[6], dp[6-1]+10) = max(0, dp[5]+10) = max(0, 50+10) = 60.
- Vật phẩm 2: dp[6] = max(60, dp[6-3]+30) = max(60, dp[3]+30) = max(60, 30+30) = 60.
- Vật phẩm 3: dp[6] = max(60, dp[6-4]+40) = max(60, dp[2]+40) = max(60, 20+40) = 60.
- dp[6] là 60. dp={0,10,20,30,40,50,60,0,0}.
w = 7:
- Vật phẩm 1: dp[7] = max(dp[7], dp[7-1]+10) = max(0, dp[6]+10) = max(0, 60+10) = 70.
- Vật phẩm 2: dp[7] = max(70, dp[7-3]+30) = max(70, dp[4]+30) = max(70, 40+30) = 70.
- Vật phẩm 3: dp[7] = max(70, dp[7-4]+40) = max(70, dp[3]+40) = max(70, 30+40) = 70.
- dp[7] là 70. dp={0,10,20,30,40,50,60,70,0}.
w = 8:
- Vật phẩm 1: dp[8] = max(dp[8], dp[8-1]+10) = max(0, dp[7]+10) = max(0, 70+10) = 80.
- Vật phẩm 2: dp[8] = max(80, dp[8-3]+30) = max(80, dp[5]+30) = max(80, 50+30) = 80.
- Vật phẩm 3: dp[8] = max(80, dp[8-4]+40) = max(80, dp[4]+40) = max(80, 40+40) = 80.
- dp[8] là 80. dp={0,10,20,30,40,50,60,70,80}.

Kết quả cuối cùng là dp[8] = 80.

Điều này có thể đạt được bằng cách lấy 8 vật phẩm loại 1 (8 w=1 = 8, 8 v=10 = 80), hoặc 2 vật phẩm loại 2 và 2 vật phẩm loại 1 (2w=3 + 2w=1 = 6+2=8, 2v=30 + 2v=10 = 60+20=80), hoặc 2 vật phẩm loại 3 (2w=4=8, 2v=40=80), v.v.

Code Minh họa 2 (C++)

Code cho ví dụ này hoàn toàn giống với code trước, chỉ khác dữ liệu đầu vào:

#include <iostream>
#include <vector>
#include <algorithm>

struct Item {
    int weight;
    int value;
};

int main() {
    // Input cho Ví dụ 2
    int W = 8; // Sức chứa túi
    std::vector<Item> items = {
        {1, 10}, // Vật phẩm 1: w=1, v=10
        {3, 30}, // Vật phẩm 2: w=3, v=30
        {4, 40}  // Vật phẩm 3: w=4, v=40
    };
    int N = items.size(); // Số loại vật phẩm

    // Mảng DP: dp[w] = giá trị lớn nhất với sức chứa w
    std::vector<int> dp(W + 1, 0);

    // Xây dựng bảng DP
    // Lặp qua từng mức sức chứa từ 1 đến W
    for (int w = 1; w <= W; ++w) {
        // Với mỗi mức sức chứa w, xét tất cả các loại vật phẩm
        for (int i = 0; i < N; ++i) {
            // Nếu vật phẩm i có thể cho vào túi (trọng lượng <= sức chứa hiện tại)
            if (items[i].weight <= w) {
                // Cập nhật dp[w]:
                // dp[w] = max(giá trị hiện tại của dp[w],
                //             giá trị đạt được nếu thêm vật phẩm i cuối cùng vào túi)
                dp[w] = std::max(dp[w], dp[w - items[i].weight] + items[i].value);
            }
        }
    }

    // Kết quả là giá trị lớn nhất có thể đạt được với sức chứa W
    std::cout << "Gia tri lon nhat voi tui suc chua " << W << " la: " << dp[W] << std::endl;

    return 0;
}

Giải thích Code 2:

Như bạn thấy, cấu trúc code hoàn toàn giống với Code 1. Sự linh hoạt của giải thuật DP là nó hoạt động với bất kỳ bộ dữ liệu đầu vào hợp lệ nào cho bài toán. Các bước khởi tạo, vòng lặp và công thức cập nhật đều tuân theo logic đã phân tích: tính toán giá trị tối ưu cho từng sức chứa tăng dần bằng cách xem xét việc thêm từng loại vật phẩm có thể.

Độ phức tạp

Độ phức tạp về Thời gian: Chúng ta có một vòng lặp ngoài chạy W lần (từ 1 đến W) và một vòng lặp trong chạy N lần (số loại vật phẩm). Bên trong vòng lặp, các thao tác là hằng số (so sánh, cộng, truy cập mảng). Do đó, độ phức tạp thời gian là O(N * W).
Độ phức tạp về Không gian: Chúng ta sử dụng một mảng DP có kích thước W + 1 để lưu trữ các giá trị trung gian. Do đó, độ phức tạp không gian là O(W).

Đây là độ phức tạp tương tự như bài toán cái túi 0/1 sử dụng DP mảng 1 chiều, cho thấy sự hiệu quả của phương pháp này.

Bài tập ví dụ:

Tiệm sách

Trong một buổi làm việc tại tiệm sách, FullHouse Dev được giao nhiệm vụ tối ưu hóa việc mua sách. Họ cần tìm cách chọn sách sao cho với số tiền giới hạn, có thể mua được nhiều trang sách nhất có thể.

Bài toán

Tiệm sách có \(n\) cuốn sách khác nhau. Mỗi cuốn sách có giá và số trang riêng. Với số tiền tối đa là \(x\), bạn cần tìm cách mua sách sao cho tổng số trang là nhiều nhất. Mỗi cuốn sách chỉ được mua tối đa một lần.

INPUT FORMAT:

Dòng đầu tiên chứa hai số nguyên \(n\) và \(x\): số lượng sách và số tiền tối đa.
Dòng thứ hai chứa \(n\) số nguyên \(h_1, h_2, ..., h_n\): giá của từng cuốn sách.
Dòng thứ ba chứa \(n\) số nguyên \(s_1, s_2, ..., s_n\): số trang của từng cuốn sách.

OUTPUT FORMAT:

In ra một số nguyên: tổng số trang tối đa có thể mua được.

Ràng buộc:

\(1 \leq n \leq 1000\)
\(1 \leq x \leq 10^5\)
\(1 \leq h_i, s_i \leq 1000\)

Ví dụ

INPUT

4 10
4 8 5 3
5 12 8 1

OUTPUT

Giải thích

Bạn có thể mua cuốn sách thứ 1 và cuốn sách thứ 3. Tổng giá tiền là 4+5=9 và tổng số trang là 5+8=13. Đây là một bài toán Cái túi 0/1 (0/1 Knapsack) cổ điển.

Vật phẩm: Mỗi cuốn sách là một vật phẩm.
Trọng lượng: Giá của cuốn sách (h_i).
Giá trị: Số trang của cuốn sách (s_i).
Sức chứa của túi: Số tiền tối đa (x).
Mục tiêu: Chọn một tập hợp sách sao cho tổng giá tiền không vượt quá x và tổng số trang là lớn nhất. Mỗi sách chỉ được chọn tối đa một lần.

Hướng giải bằng Quy hoạch động (Dynamic Programming - DP):

Định nghĩa trạng thái DP:
- Sử dụng một mảng DP, ví dụ dp có kích thước x+1.
- dp[j] sẽ lưu trữ tổng số trang tối đa có thể đạt được khi có ngân sách (tổng giá tiền) tối đa là j.
Khởi tạo:
- Khởi tạo mảng dp với tất cả các giá trị bằng 0. dp[0] = 0 (ngân sách 0 thì có 0 trang).
Công thức truy hồi (Chuyển trạng thái):
- Duyệt qua từng cuốn sách từ 1 đến n. Giả sử cuốn sách hiện tại có giá h và số trang s.
- Đối với mỗi cuốn sách, ta xét khả năng có thể mua nó hay không. Ta cập nhật mảng dp bằng cách duyệt qua các mức ngân sách j từ x xuống đến h (giá của cuốn sách hiện tại). Việc duyệt ngược lại là quan trọng trong bài toán Cái túi 0/1 để đảm bảo mỗi sách chỉ được chọn một lần.
- Đối với mỗi ngân sách j (j >= h), ta có hai lựa chọn:
  - Không mua cuốn sách hiện tại: Số trang tối đa vẫn là dp[j] (giá trị trước khi xét cuốn sách này).
  - Mua cuốn sách hiện tại: Chỉ có thể làm điều này nếu ta còn đủ ngân sách j >= h. Nếu mua, ta sử dụng ngân sách h, còn lại j - h. Số trang tối đa trong trường hợp này sẽ là dp[j - h] (số trang tối đa với ngân sách j - h, không tính cuốn sách hiện tại) cộng thêm s (số trang của cuốn sách hiện tại).
- Vậy, dp[j] mới sẽ là giá trị lớn nhất giữa hai lựa chọn: dp[j] = max(dp[j], dp[j - h] + s).
Kết quả:
- Sau khi duyệt qua tất cả n cuốn sách, giá trị dp[x] sẽ là tổng số trang tối đa có thể mua được với ngân sách tối đa là x.

Các bước thực hiện (tóm tắt):

Đọc n và x.
Đọc mảng giá h và mảng số trang s.
Tạo mảng dp kích thước x+1, khởi tạo bằng 0.
Lặp qua từng cuốn sách i từ 0 đến n-1:
- Lấy giá h_i và số trang s_i của sách i.
- Lặp qua ngân sách j từ x xuống h_i:
  - dp[j] = max(dp[j], dp[j - h_i] + s_i);
In ra dp[x].

Làm thêm nhiều bài tập miễn phí tại đây

Comments

There are no comments at the moment.