Khóa học CTDL và GT

Bài 25.2. Ứng dụng trong bài toán tổng tập con

Chào mừng trở lại với chuỗi bài viết về Cấu trúc Dữ liệu và Giải thuật! Hôm nay, chúng ta sẽ đối mặt với một bài toán tổ hợp kinh điển và vô cùng thú vị: Bài toán Tổng Tập Con (Subset Sum Problem). Bài toán này không chỉ là một thử thách lý thuyết mà còn có nhiều ứng dụng thực tế đáng ngạc nhiên.

Hãy cùng tìm hiểu xem bài toán này là gì, tại sao nó lại quan trọng, và làm thế nào chúng ta có thể giải quyết nó bằng các kỹ thuật giải thuật đã học, đặc biệt là Quay lui (Backtracking) và Lập trình Động (Dynamic Programming)!

Bài toán Tổng Tập Con là gì?

Định nghĩa một cách đơn giản, Bài toán Tổng Tập Con phát biểu như sau:

Cho một tập hợp các số nguyên $S$ và một số nguyên mục tiêu $T$. Bài toán hỏi liệu có tồn tại một tập con của $S$ mà tổng các phần tử của tập con đó bằng đúng $T$ hay không?

Ví dụ:

• Tập $S = {3, 34, 4, 12, 5, 2}$, mục tiêu $T = 9$. Tồn tại tập con ${4, 5}$ có tổng là 9. Đáp án: Có.
• Tập $S = {10, 7, 15, 12}$, mục tiêu $T = 11$. Không tồn tại tập con nào có tổng là 11. Đáp án: Không.

Một biến thể phổ biến của bài toán này là tìm tất cả các tập con có tổng bằng $T$, chứ không chỉ kiểm tra sự tồn tại.

Bài toán Tổng Tập Con là một trường hợp đặc biệt của Bài toán Ba lô (Knapsack Problem) và thuộc lớp các bài toán NP-complete. Điều này có nghĩa là chưa có giải thuật nào được biết đến có thể giải quyết bài toán này một cách hiệu quả (trong thời gian đa thức) cho mọi tập hợp và mọi giá trị mục tiêu lớn. Tuy nhiên, chúng ta vẫn có thể tìm các giải pháp hiệu quả trong thực tế cho nhiều trường hợp hoặc sử dụng các kỹ thuật như Lập trình Động để giải quyết nó trong thời gian "giả đa thức" (pseudo-polynomial time) khi giá trị mục tiêu không quá lớn.

Tiếp cận 1: Phương pháp Quay lui (Backtracking)

Phương pháp quay lui là một kỹ thuật mạnh mẽ để khám phá tất cả các khả năng có thể trong không gian tìm kiếm. Đối với Bài toán Tổng Tập Con, chúng ta có thể hình dung quá trình tìm kiếm như một cây nhị phân. Tại mỗi "nút" trong cây, tương ứng với việc xem xét một phần tử trong tập $S$, chúng ta có hai lựa chọn:

1. Bao gồm phần tử hiện tại vào tập con đang xây dựng.
2. Loại trừ phần tử hiện tại khỏi tập con đang xây dựng.

Chúng ta bắt đầu từ phần tử đầu tiên và đệ quy xuống. Chúng ta theo dõi tổng hiện tại của tập con đã được chọn. Nếu tổng hiện tại đạt được mục tiêu $T$, chúng ta đã tìm thấy một giải pháp. Nếu tổng hiện tại vượt quá $T$ (với các số dương) hoặc chúng ta đã xem xét hết tất cả các phần tử mà tổng vẫn chưa bằng $T$, chúng ta "quay lui" (backtrack) - tức là hủy bỏ lựa chọn cuối cùng và thử lựa chọn khác.

Ví dụ Quay lui (Kiểm tra sự tồn tại)

Đầu tiên, chúng ta sẽ viết code để kiểm tra xem có tồn tại một tập con có tổng bằng $T$ hay không.

#include <iostream>
#include <vector>
#include <numeric>

// Hàm đệ quy kiểm tra sự tồn tại của tập con
// set: tập các số nguyên đầu vào
// n: số lượng phần tử còn lại để xem xét (từ index n-1 trở về trước)
// targetSum: tổng mục tiêu cần đạt
bool isSubsetSum(const std::vector<int>& set, int n, int targetSum) {
    // Trường hợp cơ sở 1: Nếu tổng mục tiêu bằng 0, ta đã tìm thấy một tập con (tập con rỗng)
    // Lưu ý: Chỉ đúng khi targetSum ban đầu >= 0.
    // Nếu cho phép số âm, base case này cần được điều chỉnh.
    if (targetSum == 0) {
        return true;
    }

    // Trường hợp cơ sở 2: Nếu không còn phần tử nào để xem xét
    // và tổng mục tiêu vẫn khác 0
    if (n == 0) {
        return false;
    }

    // Trường hợp đệ quy:
    // Nếu phần tử cuối cùng (set[n-1]) lớn hơn tổng mục tiêu,
    // thì không thể bao gồm nó. Ta chỉ có lựa chọn loại trừ nó.
    if (set[n - 1] > targetSum) {
        return isSubsetSum(set, n - 1, targetSum);
    }

    // Ngược lại, có hai lựa chọn:
    // 1. Loại trừ phần tử cuối cùng: isSubsetSum(set, n-1, targetSum)
    // 2. Bao gồm phần tử cuối cùng: isSubsetSum(set, n-1, targetSum - set[n-1])
    // Nếu ít nhất một trong hai lựa chọn này dẫn đến tìm thấy tập con, thì trả về true
    return isSubsetSum(set, n - 1, targetSum) || isSubsetSum(set, n - 1, targetSum - set[n - 1]);
}

int main() {
    std::vector<int> set1 = {3, 34, 4, 12, 5, 2};
    int target1 = 9;

    std::cout << "Tap hop: {3, 34, 4, 12, 5, 2}, Muc tieu: 9" << std::endl;
    if (isSubsetSum(set1, set1.size(), target1)) {
        std::cout << "-> Ton tai tap con co tong bang 9." << std::endl;
    } else {
        std::cout << "-> Khong ton tai tap con co tong bang 9." << std::endl;
    }

    std::vector<int> set2 = {10, 7, 15, 12};
    int target2 = 11;

    std::cout << "\nTap hop: {10, 7, 15, 12}, Muc tieu: 11" << std::endl;
    if (isSubsetSum(set2, set2.size(), target2)) {
        std::cout << "-> Ton tai tap con co tong bang 11." << std::endl;
    } else {
        std::cout << "-> Khong ton tai tap con co tong bang 11." << std::endl;
    }

    std::vector<int> set3 = {1, 2, 3, 4, 5};
    int target3 = 10;

    std::cout << "\nTap hop: {1, 2, 3, 4, 5}, Muc tieu: 10" << std::endl;
    if (isSubsetSum(set3, set3.size(), target3)) {
        std::cout << "-> Ton tai tap con co tong bang 10." << std::endl; // e.g., {1, 2, 3, 4}, {1, 4, 5}, {2, 3, 5}, {1, 2, 3, 4}
    } else {
        std::cout << "-> Khong ton tai tap con co tong bang 10." << std::endl;
    }


    return 0;
}

Giải thích Code:

• Hàm isSubsetSum(set, n, targetSum) là trọng tâm của giải thuật đệ quy.
• set: Vector chứa các số nguyên đầu vào.
• n: Chỉ số (số lượng phần tử) mà chúng ta đang xem xét. Ban đầu, nó là kích thước của set. Trong các lời gọi đệ quy, nó giảm dần. set[n-1] là phần tử cuối cùng trong phạm vi xem xét hiện tại.
• targetSum: Tổng mục tiêu còn lại cần đạt.
• Base Case 1 (targetSum == 0): Nếu tổng mục tiêu đã đạt (bằng 0), nghĩa là ta đã tìm được một tập con thỏa mãn. Trả về true.
• Base Case 2 (n == 0): Nếu không còn phần tử nào để xem xét (n về 0) mà tổng mục tiêu vẫn chưa bằng 0, nghĩa là không thể tạo ra tổng đó từ các phần tử còn lại (hoặc ban đầu). Trả về false.
• Recursive Step (set[n-1] > targetSum): Nếu phần tử cuối cùng trong phạm vi xem xét (set[n-1]) lớn hơn tổng mục tiêu cần đạt (targetSum), ta không thể bao gồm phần tử này. Ta chỉ còn một lựa chọn là loại trừ nó và tiếp tục kiểm tra với n-1 phần tử còn lại.
• Recursive Step (Còn lại): Nếu phần tử cuối cùng nhỏ hơn hoặc bằng tổng mục tiêu, ta có hai lựa chọn:
  • Loại trừ (isSubsetSum(set, n-1, targetSum)): Ta bỏ qua phần tử set[n-1] và tiếp tục tìm tập con có tổng targetSum trong n-1 phần tử đầu tiên.
  • Bao gồm (isSubsetSum(set, n-1, targetSum - set[n-1])): Ta bao gồm phần tử set[n-1] vào tập con. Khi đó, tổng mục tiêu cần đạt từ n-1 phần tử đầu tiên sẽ giảm đi một lượng bằng giá trị của set[n-1].
  • Kết quả là true nếu một trong hai lựa chọn này trả về true (sử dụng toán tử ||).

Độ phức tạp của giải thuật đệ quy/quay lui này trong trường hợp xấu nhất là $O(2^n)$, vì ở mỗi bước, chúng ta rẽ nhánh thành hai khả năng cho mỗi phần tử. Điều này có thể chấp nhận được với $n$ nhỏ, nhưng sẽ rất chậm khi $n$ lớn.

Ví dụ Quay lui (Tìm tất cả tập con)

Để tìm tất cả các tập con, chúng ta cần truyền thêm một vector để lưu trữ tập con hiện tại đang được xây dựng và một vector các vector để lưu trữ tất cả các kết quả tìm được. Kỹ thuật quay lui (backtracking) trở nên rõ ràng hơn ở đây, khi chúng ta thêm một phần tử vào tập con hiện tại, đệ quy, sau đó xóa nó đi để khám phá các khả năng khác.

#include <iostream>
#include <vector>
#include <numeric>

// Hàm đệ quy tìm tất cả các tập con có tổng bằng targetSum
// set: tập các số nguyên đầu vào
// index: chỉ số của phần tử hiện tại đang xem xét
// currentSubset: vector lưu trữ tập con đang được xây dựng
// currentSum: tổng của các phần tử trong currentSubset
// targetSum: tổng mục tiêu cần đạt
// results: vector lưu trữ tất cả các tập con tìm được thỏa mãn
void findAllSubsets(const std::vector<int>& set, int index,
                    std::vector<int>& currentSubset, int currentSum,
                    int targetSum, std::vector<std::vector<int>>& results) {

    // Trường hợp cơ sở: Nếu đã xem xét hết tất cả các phần tử
    if (index == set.size()) {
        // Nếu tổng hiện tại bằng tổng mục tiêu, lưu trữ tập con này
        if (currentSum == targetSum) {
            results.push_back(currentSubset);
        }
        return; // Dừng đệ quy cho nhánh này
    }

    // Lựa chọn 1: Loại trừ phần tử hiện tại (set[index])
    findAllSubsets(set, index + 1, currentSubset, currentSum, targetSum, results);

    // Lựa chọn 2: Bao gồm phần tử hiện tại (set[index])
    currentSubset.push_back(set[index]); // Thêm phần tử vào tập con hiện tại
    findAllSubsets(set, index + 1, currentSubset, currentSum + set[index], targetSum, results);

    // *** QUAY LUI ***: Loại bỏ phần tử vừa thêm để thử các khả năng khác
    // Điều này cho phép nhánh đệ quy trước (Loại trừ) tiếp tục khám phá các tập con khác
    currentSubset.pop_back();
}

int main() {
    std::vector<int> set1 = {10, 1, 2, 7, 6, 1, 5};
    int target1 = 8;

    std::vector<std::vector<int>> results1;
    std::vector<int> currentSubset1;

    std::cout << "Tap hop: {10, 1, 2, 7, 6, 1, 5}, Muc tieu: 8" << std::endl;
    findAllSubsets(set1, 0, currentSubset1, 0, target1, results1);

    if (results1.empty()) {
        std::cout << "-> Khong tim thay tap con nao co tong bang 8." << std::endl;
    } else {
        std::cout << "-> Cac tap con co tong bang 8:" << std::endl;
        for (const auto& subset : results1) {
            std::cout << "  { ";
            for (size_t i = 0; i < subset.size(); ++i) {
                std::cout << subset[i] << (i == subset.size() - 1 ? "" : ", ");
            }
            std::cout << " }" << std::endl;
        }
    }

    std::vector<int> set2 = {1, 2, 3};
    int target2 = 4;
    std::vector<std::vector<int>> results2;
    std::vector<int> currentSubset2;

    std::cout << "\nTap hop: {1, 2, 3}, Muc tieu: 4" << std::endl;
    findAllSubsets(set2, 0, currentSubset2, 0, target2, results2);

    if (results2.empty()) {
        std::cout << "-> Khong tim thay tap con nao co tong bang 4." << std::endl;
    } else {
         std::cout << "-> Cac tap con co tong bang 4:" << std::endl;
        for (const auto& subset : results2) {
            std::cout << "  { ";
            for (size_t i = 0; i < subset.size(); ++i) {
                std::cout << subset[i] << (i == subset.size() - 1 ? "" : ", ");
            }
            std::cout << " }" << std::endl;
        }
    }

     std::vector<int> set3 = {5, 10, 15, 20, 25};
    int target3 = 30;
    std::vector<std::vector<int>> results3;
    std::vector<int> currentSubset3;

    std::cout << "\nTap hop: {5, 10, 15, 20, 25}, Muc tieu: 30" << std::endl;
    findAllSubsets(set3, 0, currentSubset3, 0, target3, results3);

     if (results3.empty()) {
        std::cout << "-> Khong tim thay tap con nao co tong bang 30." << std::endl;
    } else {
         std::cout << "-> Cac tap con co tong bang 30:" << std::endl;
        for (const auto& subset : results3) {
            std::cout << "  { ";
            for (size_t i = 0; i < subset.size(); ++i) {
                std::cout << subset[i] << (i == subset.size() - 1 ? "" : ", ");
            }
            std::cout << " }" << std::endl;
        }
    }


    return 0;
}

Giải thích Code:

• Hàm findAllSubsets có thêm các tham số để theo dõi trạng thái: currentSubset (vector các số đã chọn cho tập con hiện tại), currentSum (tổng của currentSubset), và results (vector chứa các kết quả cuối cùng).
• Base Case (index == set.size()): Khi index đạt đến kích thước của set, nghĩa là chúng ta đã xem xét qua tất cả các phần tử. Nếu currentSum lúc này bằng targetSum, chúng ta đã tìm được một tập con thỏa mãn và thêm nó vào danh sách results.
• Recursive Steps:
  • Loại trừ: Chúng ta gọi đệ quy với index + 1, giữ nguyên currentSubset và currentSum. Điều này mô phỏng việc bỏ qua set[index].
  • Bao gồm:
    • Chúng ta thêm set[index] vào currentSubset.
    • Chúng ta gọi đệ quy với index + 1, cập nhật currentSum thành currentSum + set[index].
    • Backtracking (currentSubset.pop_back()): Sau khi lời gọi đệ quy cho việc "bao gồm" hoàn thành (dù nó tìm thấy kết quả hay không), chúng ta phải xóa phần tử set[index] khỏi currentSubset. Điều này là cực kỳ quan trọng. Nó "hoàn tác" lựa chọn bao gồm để hàm có thể quay lại điểm quyết định trước đó và khám phá các khả năng khác (các tập con không chứa set[index] tại vị trí hiện tại).

Phương pháp quay lui này rất trực quan cho việc tìm tất cả các tập con. Tuy nhiên, độ phức tạp vẫn là $O(2^n \times n)$ trong trường hợp xấu nhất (vì có thể có $2^n$ tập con và việc copy/lưu trữ mỗi tập con có thể mất $O(n)$ thời gian).

Tiếp cận 2: Phương pháp Lập trình Động (Dynamic Programming)

Khi bài toán chỉ yêu cầu kiểm tra sự tồn tại của một tập con có tổng bằng $T$ (và các số trong tập hợp là không âm), chúng ta có thể sử dụng Lập trình Động để giải quyết nó hiệu quả hơn trong một số trường hợp. DP giúp tránh việc tính toán lặp lại các bài toán con giống nhau mà phương pháp đệ quy đơn giản có thể gặp phải.

Ý tưởng chính của DP cho bài toán này là xây dựng một bảng (thường là 2 chiều) để lưu trữ kết quả của các bài toán con. Chúng ta có thể định nghĩa dp[i][j] là một giá trị boolean cho biết liệu có thể tạo ra tổng j bằng cách chỉ sử dụng các phần tử từ set[0] đến set[i-1] hay không.

Kích thước của bảng DP sẽ là (n + 1) x (targetSum + 1).

Công thức truy hồi (recurrence relation): dp[i][j] = dp[i-1][j] (Có thể tạo tổng j mà không cần dùng đến set[i-1]) || dp[i-1][j - set[i-1]] (Nếu j >= set[i-1], ta có thể tạo tổng j bằng cách dùng set[i-1] và tạo tổng j - set[i-1] từ các phần tử set[0] đến set[i-2])

Các trường hợp cơ sở (base cases):

• dp[0][0] = true: Có thể tạo tổng 0 với 0 phần tử (tập rỗng).
• dp[i][0] = true cho mọi i > 0: Luôn có thể tạo tổng 0 bằng cách không chọn bất kỳ phần tử nào từ i phần tử đầu tiên.
• dp[0][j] = false cho mọi j > 0: Không thể tạo tổng dương nào nếu không có phần tử nào.

Sau khi điền đầy đủ bảng DP, kết quả cuối cùng sẽ nằm ở dp[n][targetSum].

Ví dụ Lập trình Động (Kiểm tra sự tồn tại)

#include <iostream>
#include <vector>
#include <numeric>

// Hàm DP kiểm tra sự tồn tại của tập con
// set: tập các số nguyên không âm đầu vào
// targetSum: tổng mục tiêu cần đạt
bool isSubsetSumDP(const std::vector<int>& set, int targetSum) {
    int n = set.size();

    // Tạo bảng DP: dp[i][j] là true nếu tổng j có thể đạt được
    // từ các phần tử đầu tiên (từ set[0] đến set[i-1])
    // Kích thước (n + 1) x (targetSum + 1)
    std::vector<std::vector<bool>> dp(n + 1, std::vector<bool>(targetSum + 1));

    // Khởi tạo trường hợp cơ sở:
    // dp[i][0] luôn là true (tổng 0 luôn có thể đạt được bằng tập rỗng)
    for (int i = 0; i <= n; ++i) {
        dp[i][0] = true;
    }

    // dp[0][j] luôn là false cho j > 0 (không thể đạt tổng dương nào với 0 phần tử)
    // Phần này đã được mặc định false khi khởi tạo vector<bool>

    // Điền bảng DP
    // i duyệt qua số lượng phần tử (từ 1 đến n)
    // j duyệt qua các tổng mục tiêu (từ 1 đến targetSum)
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= targetSum; ++j) {
            // Nếu không bao gồm set[i-1] (phần tử thứ i trong mảng gốc, index i-1)
            // Khả năng đạt tổng j vẫn giữ nguyên như khi chỉ dùng i-1 phần tử
            dp[i][j] = dp[i - 1][j];

            // Nếu có thể bao gồm set[i-1] (set[i-1] <= j)
            // thì khả năng đạt tổng j cũng bao gồm trường hợp ta dùng set[i-1]
            // và cần đạt tổng j - set[i-1] từ i-1 phần tử đầu tiên
            if (j >= set[i - 1]) {
                dp[i][j] = dp[i][j] || dp[i - 1][j - set[i - 1]];
            }
        }
    }

    // Kết quả cuối cùng nằm ở dp[n][targetSum]
    return dp[n][targetSum];
}

int main() {
    std::vector<int> set1 = {3, 34, 4, 12, 5, 2};
    int target1 = 9;

    std::cout << "Tap hop: {3, 34, 4, 12, 5, 2}, Muc tieu: 9" << std::endl;
    if (isSubsetSumDP(set1, target1)) {
        std::cout << "-> Ton tai tap con co tong bang 9." << std::endl; // e.g., {4, 5}
    } else {
        std::cout << "-> Khong ton tai tap con co tong bang 9." << std::endl;
    }

    std::vector<int> set2 = {10, 7, 15, 12};
    int target2 = 11;

    std::cout << "\nTap hop: {10, 7, 15, 12}, Muc tieu: 11" << std::endl;
    if (isSubsetSumDP(set2, target2)) {
        std::cout << "-> Ton tai tap con co tong bang 11." << std::endl;
    } else {
        std::cout << "-> Khong ton tai tap con co tong bang 11." << std::endl;
    }

    std::vector<int> set3 = {1, 2, 3, 4, 5};
    int target3 = 10;

    std::cout << "\nTap hop: {1, 2, 3, 4, 5}, Muc tieu: 10" << std::endl;
    if (isSubsetSumDP(set3, target3)) {
        std::cout << "-> Ton tai tap con co tong bang 10." << std::endl; 
    } else {
        std::cout << "-> Khong ton tai tap con co tong bang 10." << std::endl;
    }

    // Ví dụ với targetSum lớn
    std::vector<int> set4 = {10, 20, 30};
    int target4 = 50;
     std::cout << "\nTap hop: {10, 20, 30}, Muc tieu: 50" << std::endl;
    if (isSubsetSumDP(set4, target4)) {
        std::cout << "-> Ton tai tap con co tong bang 50." << std::endl; // {20, 30}
    } else {
        std::cout << "-> Khong ton tai tap con co tong bang 50." << std::endl;
    }


    return 0;
}

Giải thích Code:

• Hàm isSubsetSumDP(set, targetSum) sử dụng một bảng DP 2D (dp) kích thước (n+1) x (targetSum+1).
• dp[i][j] là true nếu có thể tạo ra tổng j sử dụng i phần tử đầu tiên của set (tức là set[0] đến set[i-1]).
• Khởi tạo: Cột đầu tiên (j=0) được đặt là true vì tổng 0 luôn có thể đạt được bằng tập rỗng. Hàng đầu tiên (i=0) được đặt là false cho j > 0 vì không thể đạt tổng dương nào với 0 phần tử.
• Điền bảng: Chúng ta duyệt qua từng ô dp[i][j] từ i=1 đến n và j=1 đến targetSum.
  • Giá trị dp[i][j] ban đầu được gán bằng dp[i-1][j]. Điều này đại diện cho khả năng tạo tổng j mà không sử dụng phần tử hiện tại set[i-1].
  • Nếu j đủ lớn để bao gồm set[i-1] (tức là j >= set[i-1]), chúng ta kiểm tra thêm khả năng tạo tổng j bằng cách sử dụng set[i-1]. Khả năng này tồn tại nếu chúng ta có thể tạo ra tổng còn lại (j - set[i-1]) chỉ bằng cách sử dụng i-1 phần tử đầu tiên (dp[i-1][j - set[i-1]]). Ta cập nhật dp[i][j] là true nếu ít nhất một trong hai khả năng (không dùng hoặc có dùng set[i-1]) là true.
• Sau khi điền xong bảng, dp[n][targetSum] chứa kết quả cuối cùng: liệu có thể tạo tổng targetSum bằng cách sử dụng tất cả n phần tử hay không.

Độ phức tạp thời gian của giải thuật DP này là $O(n \times T)$, và độ phức tạp không gian là $O(n \times T)$ (hoặc $O(T)$ nếu tối ưu hóa không gian). Đây là "giả đa thức" vì nó phụ thuộc vào giá trị của $T$, không chỉ là số lượng phần tử $n$. Khi $T$ rất lớn, DP có thể không hiệu quả hơn so với giải thuật mũ $O(2^n)$. Tuy nhiên, khi $T$ có giới hạn hợp lý, DP vượt trội hơn nhiều so với quay lui thô sơ. Cần lưu ý rằng DP trong ví dụ này chỉ hoạt động hiệu quả với các số không âm.

Ứng dụng thực tế

Bài toán Tổng Tập Con xuất hiện ở đâu trong thế giới thực?

• Phân bổ tài nguyên: Giả sử bạn có một ngân sách (targetSum) và một danh sách các dự án với chi phí khác nhau (các số trong tập hợp). Bạn có thể đầu tư vào dự án nào để sử dụng hết hoặc gần hết ngân sách?
• Cắt/Đóng gói: Cắt một tấm vật liệu lớn thành các mảnh có kích thước nhỏ hơn để giảm thiểu phế liệu. Hoặc đóng gói các mặt hàng có trọng lượng khác nhau vào một hộp có sức chứa giới hạn.
• Mật mã học: Liên quan đến các bài toán khó về mặt tính toán.
• Khoa học máy tính: Tối ưu hóa bộ nhớ cache, phân tích dữ liệu (tìm các nhóm dữ liệu có tổng đặc điểm nào đó).
• Tài chính: Chọn các tài sản trong danh mục đầu tư sao cho tổng giá trị hoặc tổng rủi ro đạt mức mong muốn.

Bài tập ví dụ:

Lập trình an toàn

Trong một buổi thảo luận về an ninh mạng, FullHouse Dev được giao nhiệm vụ phát triển một hệ thống kiểm tra tính an toàn của việc lưu trữ dữ liệu. Họ cần xây dựng một chương trình để đảm bảo việc biểu diễn số nguyên và các phép toán trên số nguyên không bị tràn bộ nhớ.

Bài toán

Cho \(N\) kiểu dữ liệu số nguyên không dấu có kích thước (tính bằng bit) là \(a_1\), \(a_2\), \(a_3\), ..., \(a_n\). Nếu kiểu dữ liệu thứ \(i\) có kích thước \(a_i\) bit, nó có thể lưu trữ các số từ 0 đến \(2^{a_i} - 1\).

Quy tắc lập trình an toàn như sau:

Nếu \(n\) là một số có thể biểu diễn bởi kích thước bit \(a_i\), và nếu tồn tại ít nhất một \(a_j > a_i\) trong mảng đã cho, thì \(n^3\) phải có thể biểu diễn được bởi một trong các kích thước bit trong mảng \(a\).

INPUT FORMAT:

• Dòng đầu tiên chứa số nguyên \(N\) - số lượng biến thể kích thước bit.

• Dòng thứ hai chứa \(N\) số nguyên cách nhau bởi dấu cách - các kích thước bit có sẵn.

OUTPUT FORMAT:

• In ra 1 nếu đó là lập trình an toàn, ngược lại in ra 0.

Ràng buộc:

• \(1 \leq N \leq 10^5\)

• \(1 \leq a_i \leq 32\)

Ví dụ

INPUT

4
3 10 3 3

OUTPUT

1

Giải thích

Cho:

• \(N = 4\)
• \(a = [3, 10, 3, 3]\)

Phân tích:

• Các kích thước bit cho trước là 3, 10, 3 và 3.
• Lấy \(n = 7\), số này có thể biểu diễn bởi kiểu dữ liệu có kích thước \(a_1 = 3\) bit (\(2^3 - 1 = 7\)).
• Ở đây \(a_2 = 10\) tồn tại trong mảng và \(a_2 > a_1\).
• Theo quy tắc, ta phải có thể biểu diễn \(n^3 = 343\) bằng các kích thước bit cho trước, cụ thể là 10 bit.
• Số lớn nhất có thể biểu diễn bằng 10 bit là \(2^{10} - 1 = 1023\).
• Do \(343 < 1023\) nên ta có thể biểu diễn 343 bằng các kích thước bit cho trước.
• Vì vậy kết quả là 1. ```cpp // Hướng dẫn giải bài Lập trình an toàn

// 1. Đọc dữ liệu: // - Đọc số nguyên N. // - Đọc N số nguyên là các kích thước bit a_i. Lưu các giá trị này lại. // - Do kích thước bit a_i chỉ từ 1 đến 32, ta có thể dùng một mảng boolean (hoặc set) kích thước 33 để đánh dấu sự hiện diện của từng kích thước bit độc nhất (is_present[k] = true nếu kích thước k bit có trong input).

// 2. Tìm kích thước bit lớn nhất: // - Duyệt qua mảng a_i đã đọc để tìm giá trị lớn nhất, gọi là max_a.

// 3. Kiểm tra quy tắc an toàn: // - Quy tắc cần kiểm tra cho mỗi kích thước bit a_i mà không phải là kích thước lớn nhất (tức là a_i < max_a). // - Đối với một kích thước i bit (1 <= i < max_a) có trong input, ta cần kiểm tra số lớn nhất có thể biểu diễn bằng i bit, đó là n = 2^i - 1. // - Tính n^3 = (2^i - 1)^3. // - Quy tắc yêu cầu n^3 phải biểu diễn được bằng một trong các kích thước bit đã cho. Kích thước bit lớn nhất có trong input là max_a. Nếu n^3 có thể biểu diễn được bằng max_a bit, tức là n^3 <= 2^{max_a} - 1, thì nó cũng có thể biểu diễn được. Đây là điều kiện kiểm tra đủ (nếu n^3 không biểu diễn được bằng kích thước lớn nhất, chắc chắn không biểu diễn được bằng các kích thước nhỏ hơn). // - Vì vậy, ta chỉ cần kiểm tra xem (2^i - 1)^3 có nhỏ hơn hoặc bằng 2^{max_a} - 1 hay không, cho mỗi kích thước i < max_a mà có mặt trong input.

// 4. Thực hiện kiểm tra hiệu quả: // - Duyệt qua các kích thước bit có thể có từ 1 đến 32 (hoặc cụ thể hơn là từ 1 đến max_a - 1). // - Nếu kích thước i có mặt trong input (kiểm tra mảng is_present): // - Tính giá trị max_n = (2^i - 1). Cẩn thận tràn số khi tính 2^i. Sử dụng kiểu dữ liệu 64-bit không dấu (unsigned long long) cho 2^i và các phép tính tiếp theo. max_n = (1ULL << i) - 1. // - Tính cube = max_n max_n max_n. // - Tính giới hạn cho max_a bit: limit = (1ULL << max_a) - 1. // - So sánh cube và limit. Nếu cube > limit, quy tắc bị vi phạm. In ra 0 và kết thúc chương trình ngay lập tức. // - Lưu ý tối ưu: Nếu i đủ lớn (ví dụ i >= 11, vì (2^{11}-1)^3 đã lớn hơn 2^{32}-1, mà max_a <= 32), thì (2^i-1)^3 chắc chắn lớn hơn 2^{max_a}-1 khi i < max_a. Có thể thêm kiểm tra if (i >= 11) để in 0 ngay lập tức nếu kích thước i này có mặt và i < max_a. Điều này tránh tính toán với các số quá lớn.

// 5. Kết quả: // - Nếu vòng lặp kiểm tra kết thúc mà không tìm thấy vi phạm nào, điều đó có nghĩa là quy tắc an toàn được tuân thủ cho tất cả các trường hợp cần kiểm tra. In ra 1.

// Tóm tắt các bước: // 1. Đọc N và các a_i. Dùng mảng boolean is_present[1...32] để đánh dấu sự có mặt của từng kích thước. // 2. Tìm max_a. // 3. Duyệt i từ 1 đến max_a - 1. // 4. Nếu is_present[i] là true: // a. Nếu i >= 11, in 0, kết thúc. // b. Nếu i < 11, tính (1ULL << i) - 1, lập phương, và so sánh với (1ULL << max_a) - 1. Nếu lớn hơn, in 0, kết thúc. // 5. Nếu duyệt hết mà chưa kết thúc, in 1. ```

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