Bài toán POJ 1011 Sticks: Tìm Độ Dài Gốc Nhỏ Nhất

Bài toán POJ 1011 Sticks yêu cầu chúng ta phục hồi lại các que gỗ ban đầu từ một tập hợp các mảnh đã bị cắt. Giả sử George có một số que gỗ dài bằng nhau. Anh ta cắt chúng thành nhiều mảnh nhỏ, mỗi mảnh có độ dài tối đa 50 đơn vị. George quên mất số lượng que gỗ ban đầu và độ dài chính xác của chúng. Nhiệm vụ của chúng ta là phát triển một chương trình tìm ra độ dài nhỏ nhất có thể của các que gỗ gốc. Tất cả độ dài đều là số nguyên dương.

Mô tả đầu vào

Mỗi bộ dữ liệu bao gồm hai dòng. Dòng đầu tiên chứa số lượng mảnh que gỗ (N), với N không quá 64. Dòng thứ hai liệt kê độ dài của N mảnh que gỗ đó, cách nhau bởi dấu cách. Dòng cuối cùng của tệp chứa số 0 để kết thúc.

Mô tả đầu ra

Với mỗi bộ dữ liệu, chương trình cần in ra một số nguyên duy nhất trên một dòng, đó là độ dài nhỏ nhất có thể của các que gỗ gốc.

Ví dụ

9
5 2 1 5 2 1 5 2 1
4
1 2 3 4
0

6
5

Phương pháp giải quyết

Để giải quyết bài toán này, chúng ta sẽ sử dụng phương pháp duyệt ngược (backtracking) kết hợp với các kỹ thuật tối ưu. Ý tưởng chính là thử nghiệm các giá trị có thể cho độ dài gốc của que gỗ (gọi là assumed_original_stick_length). Với mỗi assumed_original_stick_length giả định, chúng ta sẽ cố gắng ghép các mảnh que gỗ đã cho lại để tạo thành các que có độ dài đó.

Các bước thực hiện cụ thể:

1. Tổng hợp và Sắp xếp: Tính tổng độ dài của tất cả các mảnh que (total_length_sum). Sắp xếp các mảnh que theo thứ tự giảm dần. Việc này giúp tìm được các mảnh lớn trước, tăng khả năng cắt tỉa nhánh không cần thiết (pruning) trong quá trình duyệt.
2. Duyệt các Độ dài Gốc tiềm năng: Độ dài gốc nhỏ nhất có thể phải lớn hơn hoặc bằng độ dài của mảnh que dài nhất (piece_lengths[0]). Nó cũng phải là ước của total_length_sum. Chúng ta sẽ duyệt assumed_original_stick_length từ piece_lengths[0] đến total_length_sum. Khi tìm thấy độ dài nhỏ nhất thỏa mãn, chúng ta sẽ dừng lại.
3. Hàm DFS (Depth-First Search) và Backtracking:

   Đối với mỗi assumed_original_stick_length được thử nghiệm, chúng ta sử dụng một hàm đệ quy can_form_sticks để kiểm tra xem có thể ghép tất cả các mảnh que thành các que có độ dài assumed_original_stick_length hay không. Hàm này cần theo dõi số mảnh còn lại cần đặt và độ dài còn thiếu để hoàn thành que hiện tại.

4. Tối ưu hóa (Pruning):
   • Loại bỏ các mảnh trùng lặp: Nếu có nhiều mảnh cùng độ dài, và việc thử một mảnh đó không thành công, thì việc thử mảnh cùng độ dài tiếp theo trong cùng ngữ cảnh cũng sẽ không thành công. Chúng ta có thể bỏ qua các mảnh trùng lặp đã bị đánh dấu là không thành công.
   • Cắt tỉa khi không còn lựa chọn: Nếu một mảnh que không thể hoàn thành que hiện tại, hoặc nếu nó là mảnh đầu tiên của một que mới và không thể dẫn đến giải pháp, thì không cần thử các mảnh nhỏ hơn trong cùng tình huống đó. Điều này đặc biệt hiệu quả khi các mảnh đã được sắp xếp giảm dần.

Mã nguồn C++

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm> // For std::sort and std::fill

std::vector<int> piece_lengths;
std::vector<bool> piece_used;
int total_length_sum;
int number_of_pieces;
int assumed_original_stick_length;

// Hàm đệ quy kiểm tra xem có thể ghép các mảnh thành các que có độ dài 'assumed_original_stick_length' hay không
// pieces_left_to_place: số mảnh còn lại cần đặt
// current_stick_remaining_capacity: độ dài còn thiếu để hoàn thành que gỗ hiện tại
bool can_form_sticks(int pieces_left_to_place, int current_stick_remaining_capacity) {
    // Base case: Nếu tất cả các mảnh đã được đặt thành công
    if (pieces_left_to_place == 0) {
        return true;
    }

    // Nếu que gỗ hiện tại đã được hoàn thành (không còn chỗ trống)
    if (current_stick_remaining_capacity == 0) {
        // Bắt đầu xây dựng một que gỗ mới
        return can_form_sticks(pieces_left_to_place, assumed_original_stick_length);
    }

    // Vòng lặp để thử từng mảnh que gỗ
    for (int i = 0; i < number_of_pieces; ++i) {
        // Kiểm tra nếu mảnh chưa được sử dụng và có thể vừa vào que hiện tại
        if (!piece_used[i] && piece_lengths[i] <= current_stick_remaining_capacity) {
            // Tối ưu hóa: Bỏ qua các mảnh trùng lặp nếu mảnh trước đó cùng giá trị đã thất bại
            // Điều này tránh các nhánh tìm kiếm giống hệt nhau
            if (i > 0 && piece_lengths[i] == piece_lengths[i-1] && !piece_used[i-1]) {
                continue;
            }

            piece_used[i] = true; // Đánh dấu mảnh đã sử dụng
            
            // Gọi đệ quy với số mảnh còn lại và dung lượng còn thiếu mới
            if (can_form_sticks(pieces_left_to_place - 1, current_stick_remaining_capacity - piece_lengths[i])) {
                return true; // Nếu tìm thấy giải pháp, trả về true ngay lập tức
            }
            
            piece_used[i] = false; // Backtrack: Đặt lại mảnh chưa sử dụng
            
            // Tối ưu hóa: Cắt tỉa nhánh tìm kiếm
            // 1. Nếu mảnh hiện tại lấp đầy chính xác phần còn lại của que và nhánh này thất bại,
            //    thì không mảnh nhỏ hơn nào có thể hoàn thành que này thành công (vì đã sắp xếp giảm dần).
            // 2. Nếu đây là mảnh đầu tiên được đặt vào một que mới (current_stick_remaining_capacity == assumed_original_stick_length)
            //    và nhánh này thất bại, thì không mảnh nào khác (nhỏ hơn) có thể bắt đầu que mới này thành công.
            if (current_stick_remaining_capacity - piece_lengths[i] == 0 || 
                current_stick_remaining_capacity == assumed_original_stick_length) {
                return false; 
            }
        }
    }

    return false; // Không thể tìm thấy giải pháp với cấu hình hiện tại
}

int main() {
    std::ios_base::sync_with_stdio(false); // Tăng tốc độ nhập/xuất
    std::cin.tie(NULL);

    while (std::cin >> number_of_pieces && number_of_pieces != 0) {
        piece_lengths.resize(number_of_pieces);
        total_length_sum = 0;
        for (int i = 0; i < number_of_pieces; ++i) {
            std::cin >> piece_lengths[i];
            total_length_sum += piece_lengths[i];
        }

        // Sắp xếp các mảnh theo thứ tự giảm dần để tối ưu hóa quá trình duyệt ngược
        std::sort(piece_lengths.rbegin(), piece_lengths.rend());

        // Duyệt qua các độ dài gốc tiềm năng
        // Độ dài gốc phải lớn hơn hoặc bằng mảnh dài nhất và là ước của tổng độ dài
        for (int current_candidate_length = piece_lengths[0]; 
             current_candidate_length <= total_length_sum; 
             ++current_candidate_length) {
            
            // Chỉ xem xét các độ dài là ước của tổng độ dài
            if (total_length_sum % current_candidate_length == 0) {
                // Khởi tạo mảng đánh dấu các mảnh đã sử dụng
                piece_used.assign(number_of_pieces, false); // Tương đương memset 0

                assumed_original_stick_length = current_candidate_length;

                // Bắt đầu quá trình duyệt ngược để kiểm tra khả năng ghép
                // number_of_pieces: tổng số mảnh cần đặt
                // assumed_original_stick_length: độ dài còn thiếu của que đầu tiên
                if (can_form_sticks(number_of_pieces, assumed_original_stick_length)) {
                    std::cout << assumed_original_stick_length << "\n";
                    break; // Tìm thấy độ dài nhỏ nhất, thoát vòng lặp
                }
            }
        }
    }
    return 0;
}