Khóa học CTDL và GT

Bài 4.3. Candy Dividing Problem và các biến thể

Chào mừng các bạn quay trở lại với series blog của chúng ta về Cấu trúc dữ liệu và Giải thuật! Hôm nay, chúng ta sẽ đi sâu vào một lớp bài toán cực kỳ thú vị và phổ biến, thường xuất hiện trong các kỳ thi lập trình và các vấn đề thực tế liên quan đến phân bổ tài nguyên: Bài toán Chia kẹo (Candy Dividing Problem) và các biến thể của nó.

Tưởng tượng bạn có một túi kẹo, mỗi viên có một "giá trị" (có thể là cân nặng, độ ngọt, điểm số,...) khác nhau. Nhiệm vụ của bạn là chia túi kẹo này cho một hoặc nhiều người sao cho đáp ứng một điều kiện nào đó, ví dụ như tổng giá trị kẹo mỗi người nhận được là bằng nhau, hoặc tìm cách chia sao cho sự chênh lệch giữa những người nhận là nhỏ nhất.

Nghe có vẻ đơn giản phải không? Nhưng đằng sau nó là những thách thức không nhỏ, đòi hỏi chúng ta phải vận dụng các kỹ thuật giải thuật mạnh mẽ như Lập trình động (Dynamic Programming) hay Quay lui (Backtracking).

Hãy cùng bắt đầu với dạng cơ bản nhất của bài toán này!

Bài toán Phân chia tập hợp (Partition Problem)

Đây là một biến thể rất quen thuộc của Bài toán Chia kẹo. Phát biểu đầy đủ như sau:

• Đề bài: Cho một tập hợp gồm n số nguyên dương (giá trị của n viên kẹo). Hỏi có thể phân chia tập hợp này thành hai tập hợp con không giao nhau sao cho tổng giá trị của hai tập con này là bằng nhau hay không?

• Ví dụ:

  • Tập kẹo: [10, 4, 6, 3, 7, 9, 1]
  • Tổng giá trị tất cả kẹo: 10 + 4 + 6 + 3 + 7 + 9 + 1 = 40.
  • Nếu chia làm 2 phần bằng nhau, mỗi phần phải có tổng giá trị là 40 / 2 = 20.

  • Có thể chia được không? Vâng, ví dụ: Tập 1 = [10, 7, 3], Tập 2 = [4, 6, 9, 1]. Cả hai đều có tổng là 20. Vậy đáp án là Có.

  • Tập kẹo: [10, 4, 6, 3, 7, 9, 2]

  • Tổng giá trị: 10 + 4 + 6 + 3 + 7 + 9 + 2 = 41.
  • Vì tổng là số lẻ, không thể chia thành hai phần có tổng bằng nhau. Đáp án là Không.

Quan sát quan trọng: Điều kiện cần để bài toán có lời giải là tổng giá trị của tất cả kẹo phải là một số chẵn. Nếu tổng là số lẻ, chắc chắn không thể chia thành hai phần có tổng bằng nhau.

Bài toán này quy về việc tìm xem có tập con nào của tập hợp ban đầu có tổng bằng một nửa tổng giá trị toàn bộ hay không. Nếu tìm được một tập con như vậy, thì các phần tử còn lại sẽ tạo thành tập con thứ hai và tổng của nó cũng sẽ bằng một nửa tổng toàn bộ (do Tổng_Tập_con_1 + Tổng_Tập_con_2 = Tổng_Toàn_bộ).

Cách tiếp cận 1: Thử mọi khả năng (Recursive / Brute Force)

Cách đơn giản nhất để giải quyết vấn đề này là thử mọi khả năng có thể. Đối với mỗi viên kẹo, chúng ta có hai lựa chọn: hoặc đưa nó vào tập con thứ nhất, hoặc không đưa nó vào (tức là nó sẽ thuộc về tập con thứ hai).

Chúng ta có thể sử dụng kỹ thuật đệ quy (recursion) để mô phỏng quá trình này. Hàm đệ quy sẽ có các tham số: chỉ số của viên kẹo đang xét và tổng giá trị hiện tại của tập con thứ nhất. Mục tiêu của chúng ta là xem liệu có thể xây dựng được một tập con có tổng bằng Tổng_Toàn_bộ / 2 hay không.

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

// Hàm đệ quy kiểm tra xem có thể đạt được target_sum từ candies[index...] không
bool can_partition_recursive(const std::vector<int>& candies, int index, int current_sum, int target_sum) {
    // Base case: Nếu đã xét hết tất cả các viên kẹo
    if (index == candies.size()) {
        // Kiểm tra xem tổng hiện tại có bằng target_sum không
        return current_sum == target_sum;
    }

    // Lựa chọn 1: Không đưa viên kẹo candies[index] vào tập con hiện tại
    if (can_partition_recursive(candies, index + 1, current_sum, target_sum)) {
        return true;
    }

    // Lựa chọn 2: Đưa viên kẹo candies[index] vào tập con hiện tại
    // Chỉ thực hiện nếu việc thêm viên kẹo không vượt quá target_sum
    if (current_sum + candies[index] <= target_sum) {
         if (can_partition_recursive(candies, index + 1, current_sum + candies[index], target_sum)) {
             return true;
         }
    }

    // Nếu cả hai lựa chọn đều không dẫn đến lời giải
    return false;
}

bool can_partition(const std::vector<int>& candies) {
    int total_sum = std::accumulate(candies.begin(), candies.end(), 0);

    // Nếu tổng là số lẻ, không thể chia thành hai phần bằng nhau
    if (total_sum % 2 != 0) {
        return false;
    }

    int target_sum = total_sum / 2;

    // Bắt đầu đệ quy từ viên kẹo đầu tiên (index 0) với tổng hiện tại là 0
    return can_partition_recursive(candies, 0, 0, target_sum);
}

int main() {
    std::vector<int> candies1 = {10, 4, 6, 3, 7, 9, 1}; // Sum = 40, Target = 20 -> True
    std::vector<int> candies2 = {10, 4, 6, 3, 7, 9, 2}; // Sum = 41 -> False
    std::vector<int> candies3 = {1, 5, 11, 5};         // Sum = 22, Target = 11 -> True (1, 5, 5) vs (11)

    std::cout << "Candies 1 can be partitioned: " << (can_partition(candies1) ? "True" : "False") << std::endl;
    std::cout << "Candies 2 can be partitioned: " << (can_partition(candies2) ? "True" : "False") << std::endl;
    std::cout << "Candies 3 can be partitioned: " << (can_partition(candies3) ? "True" : "False") << std::endl;

    return 0;
}

Giải thích Code:

• Hàm can_partition_recursive là trái tim của phương pháp đệ quy.
  • candies: Vector chứa giá trị các viên kẹo.
  • index: Chỉ số của viên kẹo chúng ta đang xem xét.
  • current_sum: Tổng giá trị của tập con mà chúng ta đang xây dựng ở nhánh đệ quy hiện tại.
  • target_sum: Tổng mục tiêu mà tập con cần đạt tới (Tổng_Toàn_bộ / 2).
• Base Case: Khi index == candies.size(), nghĩa là chúng ta đã duyệt qua hết tất cả các viên kẹo. Lúc này, chúng ta chỉ cần kiểm tra xem current_sum có bằng target_sum hay không.
• Recursive Step: Tại mỗi index, chúng ta có hai lựa chọn:
  • Bỏ qua candies[index]: Chúng ta gọi đệ quy với index + 1 và current_sum không đổi.
  • Chọn candies[index]: Nếu việc thêm candies[index] vào current_sum không vượt quá target_sum, chúng ta gọi đệ quy với index + 1 và current_sum + candies[index].
• Nếu một trong hai nhánh đệ quy trả về true, tức là tìm thấy một cách để đạt được target_sum, hàm sẽ trả về true. Nếu cả hai đều không thành công, trả về false.
• Hàm can_partition tính tổng ban đầu, kiểm tra điều kiện tổng chẵn, và gọi hàm đệ quy ban đầu.

Độ phức tạp: Phương pháp này có độ phức tạp thời gian là O(2^n) trong trường hợp xấu nhất, vì mỗi viên kẹo có 2 lựa chọn độc lập. Với n lớn (ví dụ n > 20-25), giải pháp này sẽ trở nên quá chậm. Độ phức tạp không gian là O(n) cho ngăn xếp đệ quy.

Cách tiếp cận 2: Lập trình động (Dynamic Programming)

Nhận thấy rằng bài toán đệ quy ở trên có sự chồng lấn giữa các bài toán con (chúng ta có thể gặp lại cùng một cặp (index, current_sum) thông qua các con đường khác nhau), đây là dấu hiệu cho thấy chúng ta có thể áp dụng Lập trình động để tối ưu hóa.

Ý tưởng chính của DP ở đây là xây dựng một bảng (thường là 1D hoặc 2D) để lưu trữ kết quả của các bài toán con: "liệu có thể đạt được một tổng s nào đó bằng cách sử dụng một tập con các viên kẹo ban đầu không?".

Chúng ta sẽ sử dụng mảng DP 1 chiều để tiết kiệm bộ nhớ. Mảng dp có kích thước target_sum + 1. dp[s] sẽ là true nếu có thể tạo ra tổng s bằng cách sử dụng một tập con các viên kẹo đã xét đến thời điểm hiện tại, và false nếu ngược lại.

#include <iostream>
#include <vector>
#include <numeric>
#include <vector> // Thêm include này cho std::vector

bool can_partition_dp(const std::vector<int>& candies) {
    int total_sum = std::accumulate(candies.begin(), candies.end(), 0);

    if (total_sum % 2 != 0) {
        return false;
    }

    int target_sum = total_sum / 2;
    int n = candies.size();

    // Mảng DP 1D: dp[s] = true nếu có thể tạo ra tổng s
    // Kích thước target_sum + 1, khởi tạo tất cả là false
    std::vector<bool> dp(target_sum + 1, false);

    // Base case: Có thể tạo ra tổng 0 (bằng cách không chọn viên kẹo nào)
    dp[0] = true;

    // Duyệt qua từng viên kẹo
    for (int candy_value : candies) {
        // Cập nhật mảng dp TỪ CUỐI VỀ ĐẦU
        // Để đảm bảo mỗi viên kẹo chỉ được sử dụng một lần cho mỗi tổng s
        for (int s = target_sum; s >= candy_value; --s) {
            // Nếu có thể tạo ra tổng s - candy_value TRƯỚC KHI xét viên kẹo hiện tại,
            // thì sau khi xét viên kẹo hiện tại, ta CÓ THỂ tạo ra tổng s (bằng cách thêm viên kẹo này)
            // Hoặc nếu đã có thể tạo ra tổng s rồi (không cần viên kẹo này)
            dp[s] = dp[s] || dp[s - candy_value];
        }
    }

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

int main() {
    std::vector<int> candies1 = {10, 4, 6, 3, 7, 9, 1}; // Sum = 40, Target = 20 -> True
    std::vector<int> candies2 = {10, 4, 6, 3, 7, 9, 2}; // Sum = 41 -> False
    std::vector<int> candies3 = {1, 5, 11, 5};         // Sum = 22, Target = 11 -> True (1, 5, 5) vs (11)
    std::vector<int> candies4 = {2, 3, 5};             // Sum = 10, Target = 5 -> True (2,3) vs (5)

    std::cout << "Candies 1 can be partitioned (DP): " << (can_partition_dp(candies1) ? "True" : "False") << std::endl;
    std::cout << "Candies 2 can be partitioned (DP): " << (can_partition_dp(candies2) ? "True" : "False") << std::endl;
    std::cout << "Candies 3 can be partitioned (DP): " << (can_partition_dp(candies3) ? "True" : "False") << std::endl;
    std::cout << "Candies 4 can be partitioned (DP): " << (can_partition_dp(candies4) ? "True" : "False") << std::endl;

    return 0;
}

Giải thích Code:

• Hàm can_partition_dp bắt đầu tương tự như hàm đệ quy, tính tổng và xác định target_sum.
• std::vector<bool> dp(target_sum + 1, false);: Tạo mảng boolean dp có kích thước target_sum + 1, ban đầu tất cả đều là false.
• dp[0] = true;: Đặt dp[0] là true vì tổng 0 luôn có thể đạt được (bằng cách không chọn viên kẹo nào).
• Vòng lặp ngoài for (int candy_value : candies): Duyệt qua từng viên kẹo trong tập hợp. Mỗi viên kẹo đại diện cho một "item" mới mà chúng ta xem xét để thêm vào các tổng có thể đạt được.
• Vòng lặp trong for (int s = target_sum; s >= candy_value; --s): Duyệt qua các tổng có thể đạt được, từ target_sum trở xuống đến candy_value. Việc duyệt ngược là rất quan trọng trong DP 1D dạng này để đảm bảo rằng mỗi viên kẹo (candy_value) chỉ được sử dụng một lần trong việc tính toán dp[s] cho viên kẹo hiện tại. Nếu duyệt xuôi, một viên kẹo có thể được sử dụng nhiều lần một cách vô ý thức (giống như bài toán Balo không giới hạn số lượng).
• dp[s] = dp[s] || dp[s - candy_value];: Đây là công thức chuyển trạng thái DP. dp[s] trở thành true nếu:
  • Nó đã là true rồi (tức là tổng s đã có thể đạt được bằng các viên kẹo trước đó, không cần dùng viên kẹo hiện tại) OR
  • Tổng s - candy_value đã có thể đạt được bằng các viên kẹo trước đó. Nếu vậy, bằng cách thêm viên kẹo candy_value hiện tại vào tập con tạo ra tổng s - candy_value, chúng ta sẽ có được tổng s.
• Sau khi duyệt hết tất cả các viên kẹo, dp[target_sum] sẽ cho biết liệu có thể tạo ra tổng target_sum hay không.

Độ phức tạp:

• Thời gian: O(n * TargetSum), trong đó n là số lượng kẹo và TargetSum là tổng mục tiêu (Tổng_Toàn_bộ / 2).
• Không gian: O(TargetSum).

Phương pháp DP này hiệu quả hơn nhiều so với brute force khi TargetSum không quá lớn. Tuy nhiên, nếu giá trị của các viên kẹo rất lớn, dẫn đến TargetSum rất lớn, độ phức tạp vẫn có thể trở nên không chấp nhận được.

Biến thể 1: Bài toán Tổng tập con (Subset Sum Problem)

Đây là một biến thể rất gần gũi, và như chúng ta đã thấy, Partition Problem thực chất là một trường hợp đặc biệt của Subset Sum.

• Đề bài: Cho một tập hợp gồm n số nguyên dương (giá trị của n viên kẹo) và một số nguyên K (một tổng mục tiêu). Hỏi có tồn tại một tập con không rỗng của tập hợp ban đầu có tổng giá trị bằng đúng K hay không?

• Ví dụ:

  • Tập kẹo: [3, 34, 4, 12, 5, 2]
  • Mục tiêu K = 9.

  • Có tập con nào có tổng bằng 9 không? Vâng, [4, 5]. Đáp án là Có.

  • Tập kẹo: [3, 34, 4, 12, 5, 2]

  • Mục tiêu K = 30.
  • Có tập con nào có tổng bằng 30 không? Đáp án là Không.

Cách giải quyết Subset Sum Problem hoàn toàn tương tự như phần DP của Partition Problem. Chỉ cần thay target_sum bằng K và không cần kiểm tra điều kiện tổng chẵn ban đầu.

#include <iostream>
#include <vector>
#include <numeric> // Không cần thiết cho Subset Sum nếu không tính tổng ban đầu, nhưng giữ lại

bool can_subset_sum(const std::vector<int>& numbers, int target_sum) {
    int n = numbers.size();

    // Mảng DP 1D: dp[s] = true nếu có thể tạo ra tổng s
    // Kích thước target_sum + 1, khởi tạo tất cả là false
    std::vector<bool> dp(target_sum + 1, false);

    // Base case: Có thể tạo ra tổng 0
    dp[0] = true;

    // Duyệt qua từng số trong tập hợp
    for (int num : numbers) {
        // Cập nhật mảng dp TỪ CUỐI VỀ ĐẦU
        for (int s = target_sum; s >= num; --s) {
            dp[s] = dp[s] || dp[s - num];
        }
    }

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

int main() {
    std::vector<int> numbers1 = {3, 34, 4, 12, 5, 2};
    int target1 = 9;  // True (4, 5)
    int target2 = 30; // False

    std::vector<int> numbers2 = {10, 20, 30, 40};
    int target3 = 60; // True (20, 40) or (10, 20, 30)

    std::cout << "Can subset sum to " << target1 << " (Numbers 1): " << (can_subset_sum(numbers1, target1) ? "True" : "False") << std::endl;
    std::cout << "Can subset sum to " << target2 << " (Numbers 1): " << (can_subset_sum(numbers1, target2) ? "True" : "False") << std::endl;
    std::cout << "Can subset sum to " << target3 << " (Numbers 2): " << (can_subset_sum(numbers2, target3) ? "True" : "False") << std::endl;

    return 0;
}

Giải thích Code:

Code này gần như giống hệt với code DP cho Partition Problem, chỉ khác là chúng ta nhận trực tiếp target_sum làm tham số thay vì tính từ tổng toàn bộ. Logic DP hoàn toàn giữ nguyên.

Độ phức tạp: Tương tự như DP cho Partition Problem:

• Thời gian: O(n * TargetSum).
• Không gian: O(TargetSum).

Biến thể 2: Chia thành k phần bằng nhau (Partition into k Equal Sums)

Bài toán này mở rộng Partition Problem cho trường hợp chia thành nhiều hơn 2 phần.

• Đề bài: Cho một tập hợp gồm n số nguyên dương (giá trị của n viên kẹo) và một số nguyên dương k. Hỏi có thể phân chia tập hợp này thành k tập hợp con không giao nhau sao cho tổng giá trị của mỗi tập con này là bằng nhau hay không?

• Ví dụ:

  • Tập kẹo: [4, 3, 2, 5, 2, 1]
  • k = 3

  • Tổng giá trị: 4 + 3 + 2 + 5 + 2 + 1 = 17. Không chia hết cho 3. Đáp án: Không.

  • Tập kẹo: [4, 3, 2, 5, 2, 1, 6]

  • Tổng giá trị: 4 + 3 + 2 + 5 + 2 + 1 + 6 = 23. Không chia hết cho 3. Đáp án: Không.

  • Tập kẹo: [4, 3, 2, 5, 2, 1, 5]

  • Tổng giá trị: 4 + 3 + 2 + 5 + 2 + 1 + 5 = 22. Chia hết cho 2, nhưng không chia hết cho 3.
  • k = 2: Yes, [4,3,2,2] vs [5,1,5] (sum 11 vs 11)

  • k = 3: Total sum = 22. Target sum per partition = 22/3 (không nguyên). Impossible -> False.

  • Tập kẹo: [4, 3, 2, 5, 2, 1, 5, 4]

  • Tổng giá trị: 4 + 3 + 2 + 5 + 2 + 1 + 5 + 4 = 26.
  • k = 2: Yes, [4,3,2,5] vs [2,1,5,4] (sum 14 vs 12). Oops, unequal sums. Is partition into two equal possible? Sum 26 -> target 13. Yes, e.g., [4,3,2,1,3 (not in list)]... Hmm, let's re-check example with equal partitions.
  • Ví dụ tốt hơn: Tập kẹo: [4, 3, 2, 5, 2, 1, 5, 4] Sum = 26.
  • k = 2: Target 13. Yes, e.g., [4, 4, 5] vs [3, 2, 2, 1, 5 (oops, already used)]. Let's recheck the set... Okay, set is [4, 3, 2, 5, 2, 1, 5, 4]. Sum is 26. k=2, target 13. Yes: [4, 4, 3, 2] (13) vs [5, 2, 1, 5] (13). True.
  • k = 3: Total sum = 26. Không chia hết cho 3. False.

  • k = 4: Total sum = 26. Không chia hết cho 4. False.

  • Ví dụ khác: Tập kẹo: [17, 10, 15, 10, 13, 12, 10, 20, 17, 14]

  • Tổng giá trị: 138.
  • k = 3: Target sum = 138 / 3 = 46. Có thể chia thành 3 phần, mỗi phần tổng 46 không? Đây là bài toán khó hơn.

Điều kiện cần: Tương tự như Partition Problem, tổng giá trị của tất cả kẹo phải chia hết cho k. Nếu không, đáp án chắc chắn là Không. Nếu chia hết, tổng mục tiêu cho mỗi phần là target_sum = Tổng_Toàn_bộ / k.

Bài toán này khó hơn Partition Problem (k=2) và Subset Sum. DP 1D hay 2D đơn giản như trên không đủ sức. Thay vào đó, chúng ta thường phải dùng kỹ thuật Quay lui (Backtracking), có cải tiến.

Ý tưởng là thử lần lượt đặt từng viên kẹo vào một trong k nhóm (ban đầu rỗng). Chúng ta cần theo dõi tổng hiện tại của mỗi nhóm.

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm> // Để sắp xếp

// Hàm đệ quy/quay lui để cố gắng đặt viên kẹo index vào một trong k nhóm
bool can_partition_k_recursive(std::vector<int>& candies, int index, std::vector<int>& subset_sums, int target_sum_per_subset) {
    // Base case: Nếu đã xét hết tất cả các viên kẹo
    if (index == -1) { // Duyệt ngược từ viên kẹo lớn nhất
        // Kiểm tra xem tất cả các nhóm có đạt target_sum_per_subset không (trừ nhóm đầu tiên,
        // vì nếu k-1 nhóm đạt target, và tổng ban đầu chia hết cho k, thì nhóm cuối cùng cũng đạt)
        for (size_t i = 0; i < subset_sums.size() - 1; ++i) {
            if (subset_sums[i] != target_sum_per_subset) {
                return false;
            }
        }
        return true; // Tất cả k-1 nhóm đã đạt target_sum_per_subset
    }

    // Cố gắng đặt candies[index] vào từng nhóm
    for (size_t i = 0; i < subset_sums.size(); ++i) {
        // Nếu thêm candies[index] vào nhóm i không vượt quá target_sum
        if (subset_sums[i] + candies[index] <= target_sum_per_subset) {
            subset_sums[i] += candies[index]; // Thử thêm
            // Quay lui: Nếu tìm thấy lời giải khi đặt viên kẹo này vào nhóm i
            if (can_partition_k_recursive(candies, index - 1, subset_sums, target_sum_per_subset)) {
                return true; // Tìm thấy lời giải
            }
            subset_sums[i] -= candies[index]; // Hoàn tác (backtrack)
        }

        // Tối ưu 1: Nếu nhóm i có tổng hiện tại bằng 0, và việc thêm candies[index] vào đó không tìm thấy lời giải,
        // thì việc thêm candies[index] vào bất kỳ nhóm rỗng nào khác cũng sẽ thất bại theo cùng một cách.
        // Do đó, chúng ta không cần thử các nhóm rỗng khác sau khi nhóm rỗng đầu tiên thất bại.
        if (subset_sums[i] == 0) {
             break;
        }
         // Tối ưu 2: Nếu nhóm i có tổng hiện tại bằng target_sum (đã hoàn thành một nhóm),
         // và việc thêm candies[index] vào đó (rõ ràng là không thể vì vượt quá)
         // không tìm thấy lời giải (điều kiện if ở trên đã xử lý),
         // thì việc thêm candies[index] vào bất kỳ nhóm đã hoàn thành nào khác cũng sẽ thất bại tương tự.
         // Tuy nhiên, điều này thường được bao hàm bởi Tối ưu 1 (nếu nhóm hoàn thành và nhóm rỗng đều thất bại, thì các nhóm khác cũng vậy, hoặc nhóm hoàn thành không cần xét nữa).
         // Tối ưu 1 mạnh hơn và đủ.
         // Một tối ưu khác liên quan đến trùng lặp tổng: Nếu subset_sums[i] == subset_sums[i-1] sau khi thử thêm candies[index] vào i-1 và thất bại, không cần thử i.
         // Điều này cần sắp xếp subset_sums hoặc kiểm tra cẩn thận hơn. Với cách tiếp cận hiện tại, tối ưu subset_sums[i] == 0 là đủ hiệu quả.
    }

    // Nếu không thể đặt viên kẹo candies[index] vào bất kỳ nhóm nào một cách thành công
    return false;
}


bool can_partition_k(std::vector<int>& candies, int k) {
    int total_sum = std::accumulate(candies.begin(), candies.end(), 0);

    // Điều kiện cần: tổng phải chia hết cho k và k phải dương
    if (k <= 0 || total_sum % k != 0) {
        return false;
    }

    int target_sum_per_subset = total_sum / k;

    // Nếu có viên kẹo nào lớn hơn target_sum_per_subset, không thể chia
    for (int candy : candies) {
        if (candy > target_sum_per_subset) {
            return false;
        }
    }

    // Sắp xếp các viên kẹo giảm dần. Giúp pruning (cắt tỉa) không gian tìm kiếm sớm hơn.
    // Đặt các viên kẹo lớn vào nhóm trước có xu hướng làm đầy các nhóm nhanh hơn.
    std::sort(candies.rbegin(), candies.rend());

    // Vector lưu tổng hiện tại của mỗi nhóm
    std::vector<int> subset_sums(k, 0);

    // Bắt đầu quay lui từ viên kẹo lớn nhất (ở index n-1 sau khi sort giảm dần, hoặc 0 nếu sort tăng dần)
    // Duyệt ngược từ viên cuối cùng (đã sort giảm dần)
    return can_partition_k_recursive(candies, candies.size() - 1, subset_sums, target_sum_per_subset);
}

int main() {
    std::vector<int> candies1 = {4, 3, 2, 5, 2, 1, 5, 4};
    int k1 = 4; // Sum = 26, not divisible by 4 -> False

    std::vector<int> candies2 = {4, 3, 2, 5, 2, 1, 5};
    int k2 = 3; // Sum = 22, not divisible by 3 -> False

    std::vector<int> candies3 = {4, 3, 2, 5, 2, 1, 5, 4};
    int k3 = 2; // Sum = 26, target 13 -> True ({4,4,3,2}, {5,2,1,5})

    std::vector<int> candies4 = {17, 10, 15, 10, 13, 12, 10, 20, 17, 14};
    int k4 = 3; // Sum = 138, target 46 -> True? (This is a known tough example)

    std::vector<int> candies5 = {1, 1, 1, 1, 2, 2, 2, 2};
    int k5 = 4; // Sum = 12, target 3 -> True ({1,2}, {1,2}, {1,2}, {1,2})

    std::cout << "Candies 1 can be partitioned into " << k1 << " equal parts: " << (can_partition_k(candies1, k1) ? "True" : "False") << std::endl;
    std::cout << "Candies 2 can be partitioned into " << k2 << " equal parts: " << (can_partition_k(candies2, k2) ? "True" : "False") << std::endl;
    std::cout << "Candies 3 can be partitioned into " << k3 << " equal parts: " << (can_partition_k(candies3, k3) ? "True" : "False") << std::endl;
    std::cout << "Candies 4 can be partitioned into " << k4 << " equal parts: " << (can_partition_k(candies4, k4) ? "True" : "False") << std::endl; // This one is True
    std::cout << "Candies 5 can be partitioned into " << k5 << " equal parts: " << (can_partition_k(candies5, k5) ? "True" : "False") << std::endl;


    return 0;
}

Giải thích Code:

• Hàm can_partition_k kiểm tra các điều kiện cơ bản (k > 0, tổng chia hết cho k, không có viên kẹo nào lớn hơn tổng mục tiêu mỗi phần). Nó tính target_sum_per_subset.
• std::sort(candies.rbegin(), candies.rend());: Sắp xếp các viên kẹo giảm dần. Đây là một tối ưu quan trọng cho thuật toán quay lui này. Bằng cách đặt các viên kẹo lớn trước, chúng ta có thể nhanh chóng lấp đầy các nhóm hoặc sớm nhận ra rằng không thể đặt một viên kẹo lớn nào đó vào bất kỳ nhóm còn lại nào mà không vượt quá giới hạn, giúp "cắt tỉa" không gian tìm kiếm hiệu quả hơn.
• std::vector<int> subset_sums(k, 0);: Vector này lưu trữ tổng hiện tại của mỗi trong k nhóm.
• Hàm can_partition_k_recursive là hàm quay lui:
  • candies: Vector các viên kẹo (đã sắp xếp).
  • index: Chỉ số của viên kẹo đang được xem xét để đặt vào nhóm. Bắt đầu từ candies.size() - 1 (viên lớn nhất).
  • subset_sums: Vector tổng hiện tại của các nhóm (được truyền theo tham chiếu để cập nhật).
  • target_sum_per_subset: Tổng mục tiêu cho mỗi nhóm.
  • Base Case: Khi index == -1, nghĩa là tất cả các viên kẹo đã được đặt thành công vào các nhóm. Chúng ta chỉ cần kiểm tra xem tất cả các nhóm (trừ nhóm cuối cùng) có đạt được target_sum_per_subset không. Nếu k-1 nhóm đạt được tổng mục tiêu và tổng toàn bộ chia hết cho k, thì nhóm cuối cùng chắc chắn cũng đạt được tổng mục tiêu.
  • Recursive Step: Với viên kẹo candies[index], chúng ta thử đặt nó vào từng nhóm từ i = 0 đến k-1.
    • Nếu subset_sums[i] + candies[index] <= target_sum_per_subset: Việc thêm kẹo này vào nhóm i là hợp lệ.
      • Thêm viên kẹo: subset_sums[i] += candies[index];
      • Gọi đệ quy/quay lui cho viên kẹo tiếp theo (index - 1).
      • Nếu lời gọi đệ quy trả về true, nghĩa là tìm thấy cách phân chia thành công từ trạng thái này, chúng ta trả về true ngay lập tức.
      • Nếu lời gọi đệ quy trả về false, nghĩa là cách đặt viên kẹo candies[index] vào nhóm i này không dẫn đến lời giải. Chúng ta hoàn tác việc thêm kẹo: subset_sums[i] -= candies[index]; (backtrack).
    • Tối ưu if (subset_sums[i] == 0) break;: Nếu chúng ta thử đặt viên kẹo vào nhóm i (đang rỗng) và nó không dẫn đến lời giải, thì việc thử đặt viên kẹo đó vào bất kỳ nhóm rỗng nào khác (tức là các nhóm j > i mà subset_sums[j] == 0) cũng sẽ thất bại theo cùng một cách (các trạng thái con sẽ giống nhau). Vì vậy, chúng ta có thể dừng việc thử các nhóm rỗng tiếp theo và chuyển sang viên kẹo khác.
  • Nếu sau khi thử đặt candies[index] vào tất cả các nhóm (hoặc dừng sớm nhờ tối ưu) mà không tìm thấy lời giải, hàm trả về false.

Độ phức tạp:

• Bài toán Chia k phần bằng nhau nói chung là một bài toán NP-khó.
• Thời gian: Độ phức tạp của thuật toán quay lui này trong trường hợp xấu nhất vẫn là O(k^n) (mỗi viên kẹo có k lựa chọn nhóm). Tuy nhiên, nhờ việc sắp xếp và cắt tỉa (pruning), hiệu suất thực tế thường tốt hơn nhiều, đặc biệt với dữ liệu có cấu trúc phù hợp. Nó có thể coi là O(n k^(n-k) k!) trong một số phân tích sâu hơn hoặc O(k^n) đơn giản.
• Không gian: O(n + k) cho ngăn xếp đệ quy và vector subset_sums.

So với Partition Problem (k=2), khi k tăng lên, độ khó của bài toán tăng theo cấp số nhân, và thuật toán quay lui là một trong những cách tiếp cận phổ biến, dù vẫn mang tính mũ.

Bài tập ví dụ:

Nhà sư bối rối

Trong một buổi tham quan nhà sách, FullHouse Dev được chủ nhà sách giao cho một bài toán thú vị về dãy số. Để kiểm tra khả năng tư duy của nhóm, chủ nhà sách đã đưa ra một danh sách các số và yêu cầu họ thực hiện một phép tính đặc biệt.

Bài toán

FullHouse Dev được cung cấp một danh sách \(N\) số nguyên. Họ cần tính toán một phương trình dựa trên hai hàm:

• \(g(x)\) là ước chung lớn nhất (GCD) của tất cả các số trong danh sách
• \(f(x)\) là tích của tất cả các số trong danh sách
• Giá trị MonkQuotient là \(10^9 + 7\)

Phương trình cần giải là: \((f(x)^{g(x)}) \bmod \text{MonkQuotient}\)

INPUT FORMAT:

• Dòng đầu tiên chứa số nguyên \(N\)
• Dòng thứ hai chứa \(N\) số nguyên là các phần tử trong danh sách

OUTPUT FORMAT:

• In ra kết quả của phương trình

Ràng buộc:

• \(1 \leq N \leq 50\)
• \(1 \leq A_i \leq 10^3\)

Ví dụ

INPUT

2
2 6

OUTPUT

144

Giải thích

Trong ví dụ này:

• Tích của các phần tử trong mảng là 12 (\(f(x) = 2 * 6 = 12\))
• Ước chung lớn nhất của mảng là 2 (\(g(x) = GCD(2,6) = 2\))
• Do đó, kết quả là \(12^2 = 144\)

Contributers: Chào bạn, đây là hướng dẫn giải bài "Nhà sư bối rối" bằng C++ một cách ngắn gọn:

1. Đọc input: Đọc số nguyên N và sau đó đọc N số nguyên vào một mảng hoặc vector.

2. Tính Tích (f(x)) theo modulo:

   • Khởi tạo một biến tich (hoặc tên khác) bằng 1.
   • Định nghĩa modulo M = 10^9 + 7.
   • Duyệt qua từng số A_i trong danh sách input. Với mỗi số A_i, cập nhật tich = (tich * A_i) % M.
   • Sau khi duyệt hết, biến tich sẽ chứa giá trị của f(x) mod M.

3. Tính Ước chung lớn nhất (g(x)):

   • Khởi tạo một biến gcd_val (hoặc tên khác) bằng số đầu tiên trong danh sách (A_1).
   • Sử dụng thuật toán Euclid để tính GCD. Cần một hàm int gcd(int a, int b) implement thuật toán Euclid.
   • Duyệt qua các số còn lại trong danh sách (từ A_2 đến A_N). Với mỗi số A_i, cập nhật gcd_val = gcd(gcd_val, A_i).
   • Sau khi duyệt hết, biến gcd_val sẽ chứa giá trị của g(x).

4. Tính Lũy thừa Modulo (f(x)^g(x) mod M):

   • Bạn cần tính (tich)^gcd_val % M.
   • Sử dụng thuật toán lũy thừa nhị phân (binary exponentiation hoặc exponentiation by squaring) để tính base^exponent % modulus một cách hiệu quả. Viết một hàm long long power(long long base, long long exp, long long mod).
   • Gọi hàm này với base = tich, exp = gcd_val, mod = M.

5. In kết quả: In ra giá trị trả về từ hàm power.

Tóm tắt các hàm/kỹ thuật cần dùng:

• Đọc input cơ bản.
• Tính tích liên tục đồng thời lấy modulo để tránh tràn số.
• Hàm gcd(a, b) sử dụng thuật toán Euclid.
• Hàm power(base, exp, mod) sử dụng thuật toán lũy thừa nhị phân.

Lưu ý: Sử dụng kiểu dữ liệu phù hợp (long long) cho các biến trung gian trong phép nhân modulo và hàm power để đảm bảo kết quả chính xác trước khi lấy modulo cuối cùng.

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