Khóa học CTDL và GT

#include <iostream>
#include <vector>
#include <string>

// Hàm kiểm tra xem có an toàn khi đặt Hậu tại board[row][col] không
bool isSafe(const std::vector<std::vector<int>>& board, int row, int col, int N) {
    // Kiểm tra hàng bên trái: Nếu có quân Hậu nào ở cùng hàng về phía bên trái cột hiện tại
    for (int i = 0; i < col; ++i) {
        if (board[row][i]) return false;
    }

    // Kiểm tra đường chéo trên bên trái: Nếu có quân Hậu nào trên đường chéo này
    for (int i = row, j = col; i >= 0 && j >= 0; --i, --j) {
        if (board[i][j]) return false;
    }

    // Kiểm tra đường chéo dưới bên trái: Nếu có quân Hậu nào trên đường chéo này
    for (int i = row, j = col; i < N && j >= 0; ++i, --j) {
        if (board[i][j]) return false;
    }

    // Nếu không vi phạm ràng buộc nào, vị trí này an toàn
    return true;
}

// Hàm đệ quy giải bài toán N-Queens
// col: cột hiện tại chúng ta đang cố gắng đặt quân Hậu vào
// board: ma trận biểu diễn bàn cờ
// N: kích thước bàn cờ
// Hàm trả về true nếu tìm thấy một giải pháp, false nếu không có giải pháp từ trạng thái hiện tại
bool solveNQueensUtil(std::vector<std::vector<int>>& board, int col, int N) {
    // Điều kiện cơ sở: Nếu tất cả các quân Hậu đã được đặt thành công (đã xét xong N cột)
    if (col >= N) {
        // Tìm thấy một giải pháp. Trong ví dụ này, chúng ta chỉ cần in ra một giải pháp
        // và có thể dừng lại. Để tìm tất cả các giải pháp, cần thay đổi logic ở đây.
        return true;
    }

    // Duyệt qua từng hàng trong cột hiện tại (từ 0 đến N-1) để thử đặt quân Hậu
    for (int i = 0; i < N; ++i) {
        // Kiểm tra xem việc đặt quân Hậu tại board[i][col] có an toàn không
        if (isSafe(board, i, col, N)) {
            // Nếu an toàn, "thử" đặt quân Hậu vào vị trí này
            board[i][col] = 1;

            // Gọi đệ quy để giải quyết cho cột tiếp theo (col + 1)
            if (solveNQueensUtil(board, col + 1, N)) {
                 // Nếu lời gọi đệ quy trả về true (nghĩa là tìm thấy giải pháp từ đây),
                 // thì chúng ta cũng trả về true (nếu chỉ cần tìm 1 giải pháp).
                 return true;
            }

            // Nếu lời gọi đệ quy cho cột col + 1 trả về false (nghĩa là không có cách đặt Hậu
            // từ trạng thái hiện tại để có giải pháp), chúng ta phải "quay lui" (backtrack).
            // Bỏ quân Hậu vừa đặt ở board[i][col] để thử hàng khác trong cùng cột.
            board[i][col] = 0; // Đây là bước QUAY LUI
        }
    }

    // Nếu đã thử hết tất cả các hàng trong cột hiện tại mà không tìm thấy vị trí an toàn
    // hoặc không tìm thấy giải pháp từ các vị trí đó, trả về false.
    return false;
}

// Hàm chính để bắt đầu giải bài toán N-Queens
void solveNQueens(int N) {
    // Khởi tạo bàn cờ N x N với tất cả ô đều trống (giá trị 0)
    std::vector<std::vector<int>> board(N, std::vector<int>(N, 0));

    // Bắt đầu tìm kiếm từ cột đầu tiên (cột 0)
    if (solveNQueensUtil(board, 0, N) == false) {
        std::cout << "Khong tim thay giai phap cho N = " << N << std::endl;
        // Lưu ý: Để tìm *tất cả* các giải pháp, hàm solveNQueensUtil cần được thay đổi.
        // Khi col >= N, thay vì return true, ta in ra bảng và sau đó tiếp tục
        // quá trình quay lui bằng cách luôn luôn return false (hoặc không return gì cả)
        // để khám phá các nhánh khác.
    } else {
        // Nếu solveNQueensUtil trả về true, nghĩa là đã tìm thấy ít nhất một giải pháp.
        // In ra bàn cờ biểu diễn giải pháp đó.
        std::cout << "Mot giai phap cho N = " << N << ":" << std::endl;
         for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                std::cout << (board[i][j] ? "Q " : ". "); // In 'Q' nếu có Hậu, '.' nếu trống
            }
            std::cout << std::endl;
        }
    }
}

int main() {
    int N = 4; // Thử giải bài toán 4 Quân Hậu
    std::cout << "---------- Bai toan N-Queens (N=" << N << ") ----------" << std::endl;
    solveNQueens(N);

    std::cout << std::endl;

    N = 8; // Có thể thử với N lớn hơn, nhưng thời gian chạy sẽ tăng đáng kể
    // std::cout << "---------- Bai toan N-Queens (N=" << N << ") ----------" << std::endl;
    // solveNQueens(N); // Uncomment để chạy thử với N=8

    return 0;
}

#include <iostream>
#include <vector>
#include <numeric> // Không cần thiết cho logic quay lui, nhưng có thể hữu ích cho các biến thể

// Hàm đệ quy giải bài toán Subset Sum
// index: chỉ mục của phần tử đang xét trong tập hợp ban đầu
// currentSum: tổng của các phần tử đã chọn vào tập con hiện tại
// targetSum: tổng mục tiêu cần đạt
// subset: vector lưu trữ các phần tử của tập con đang xây dựng
// set: tập hợp ban đầu chứa các số nguyên
void findSubsetsUtil(size_t index, int currentSum, int targetSum,
                     std::vector<int>& subset, const std::vector<int>& set) {

    // Điều kiện cơ sở 1: Nếu tổng hiện tại đã bằng tổng mục tiêu, chúng ta đã tìm thấy một tập con hợp lệ
    if (currentSum == targetSum) {
        std::cout << "Tim thay tap con: ";
        for (size_t i = 0; i < subset.size(); ++i) {
            std::cout << subset[i] << (i == subset.size() - 1 ? "" : ", ");
        }
        std::cout << std::endl;
        // Quan trọng: Không return ở đây nếu bạn muốn tìm TẤT CẢ các tập con
        // mà chỉ tìm một tập con. Để tìm tất cả, cứ in ra và tiếp tục quá trình quay lui.
        // Ví dụ này tìm TẤT CẢ các tập con.
    }

    // Điều kiện cơ sở 2: Nếu đã duyệt hết tất cả các phần tử trong tập hợp ban đầu
    if (index == set.size()) {
        return; // Dừng nhánh tìm kiếm này
    }

    // Pruning đơn giản: Nếu tổng hiện tại cộng với các phần tử còn lại (tối đa)
    // vẫn không đủ đạt targetSum, hoặc đã vượt quá targetSum, có thể dừng sớm.
    // Tuy nhiên, trong cài đặt đơn giản này, ta chỉ kiểm tra sau khi thêm hoặc không thêm.
    // Một cách pruning phổ biến hơn cho Subset Sum là kiểm tra currentSum > targetSum.
     if (currentSum > targetSum) {
         return;
     }


    // Lựa chọn 1: Bao gồm phần tử set[index] vào tập con hiện tại
    subset.push_back(set[index]);
    // Gọi đệ quy với index tiếp theo, tổng hiện tại tăng thêm giá trị của phần tử vừa thêm
    findSubsetsUtil(index + 1, currentSum + set[index], targetSum, subset, set);
    // **QUAY LUI**: Sau khi khám phá nhánh bao gồm set[index], chúng ta loại bỏ nó
    // khỏi tập con để chuẩn bị cho lựa chọn thứ 2 (không bao gồm nó).
    subset.pop_back();


    // Lựa chọn 2: Không bao gồm phần tử set[index] vào tập con hiện tại
    // Gọi đệ quy với index tiếp theo, tổng hiện tại giữ nguyên
    findSubsetsUtil(index + 1, currentSum, targetSum, subset, set);
}

// Hàm chính để bắt đầu tìm kiếm các tập con
void findSubsets(const std::vector<int>& set, int targetSum) {
    std::vector<int> subset; // Vector để lưu trữ tập con đang được xây dựng
    // Bắt đầu tìm kiếm từ phần tử đầu tiên (index 0), tổng ban đầu là 0
    findSubsetsUtil(0, 0, targetSum, subset, set);
}

int main() {
    std::vector<int> set = {10, 7, 5, 18, 12, 20, 15};
    int targetSum = 35;

    std::cout << "---------- Bai toan Subset Sum ----------" << std::endl;
    std::cout << "Tim cac tap con co tong bang " << targetSum << " tu tap { ";
     for (size_t i = 0; i < set.size(); ++i) {
        std::cout << set[i] << (i == set.size() - 1 ? "" : ", ");
    }
    std::cout << " }:" << std::endl;

    findSubsets(set, targetSum);

    return 0;
}

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

struct Item {
    int weight;
    int value;
    double ratio; // value/weight ratio, used for bounding
};

// Hàm so sánh cho việc sắp xếp (giảm dần theo ratio)
bool compareItems(const Item& a, const Item& b) {
    return a.ratio > b.ratio;
}

// Hàm tính cận trên (Upper Bound) cho một nhánh
// currentWeight: trọng lượng hiện tại trong túi của nhánh đang xét
// currentValue: giá trị hiện tại trong túi của nhánh đang xét
// index: chỉ mục của món đồ BẮT ĐẦU tính cận (các món đồ từ index trở đi)
// W: sức chứa tối đa của túi
// items: danh sách các món đồ (đã sắp xếp theo ratio giảm dần)
double calculateBound(int currentWeight, int currentValue, int index, int W, const std::vector<Item>& items) {
    double bound = currentValue; // Giá trị khởi đầu của cận là giá trị đã có
    int totalWeight = currentWeight; // Trọng lượng đã có

    // Duyệt qua các món đồ còn lại (từ index trở đi) để tính cận theo kiểu Fractional Knapsack
    for (size_t i = index; i < items.size(); ++i) {
        // Nếu có thể thêm toàn bộ món đồ items[i]
        if (totalWeight + items[i].weight <= W) {
            totalWeight += items[i].weight;
            bound += items[i].value;
        } else {
            // Nếu không đủ chỗ cho toàn bộ món đồ, thêm một phần của nó
            // (fractional) để lấp đầy trọng lượng còn lại và tính giá trị tương ứng.
            // Đây chính là điểm mấu chốt của việc tính cận bằng Fractional Knapsack.
            int remainingWeight = W - totalWeight;
            bound += remainingWeight * items[i].ratio;
            break; // Túi đã "đầy" (với fractional item cuối cùng)
        }
    }
    return bound;
}

// Hàm đệ quy giải bài toán Knapsack bằng Nhánh cận
// index: chỉ mục của món đồ đang xét quyết định (có cho vào túi hay không)
// currentWeight: trọng lượng hiện tại trong túi
// currentValue: giá trị hiện tại trong túi
// W: sức chứa tối đa của túi
// items: danh sách các món đồ (đã sắp xếp theo ratio)
// max_value: biến tham chiếu để lưu trữ giá trị tối ưu tìm được cho đến nay
void knapsackUtil(size_t index, int currentWeight, int currentValue, int W,
                  const std::vector<Item>& items, int& max_value) {

    // Cập nhật giá trị tối đa tìm được nếu giải pháp hiện tại tốt hơn
    // (Giải pháp được xem xét khi đã xét hết các món đồ hoặc tại bất kỳ nút nào)
    if (currentValue > max_value) {
        max_value = currentValue;
    }

    // Điều kiện dừng: Đã xét hết tất cả các món đồ
    if (index == items.size()) {
        return;
    }

    // ------ Lựa chọn 1: Bao gồm món đồ items[index] vào túi (nếu có đủ chỗ) ------
    // Chỉ xét nếu trọng lượng hiện tại cộng trọng lượng món đồ không vượt quá sức chứa
    if (currentWeight + items[index].weight <= W) {
        int nextWeight = currentWeight + items[index].weight;
        int nextValue = currentValue + items[index].value;

        // Tính cận trên cho nhánh CÓ bao gồm items[index]
        // Cận này dựa trên trạng thái sau khi thêm items[index] và các món đồ còn lại từ index+1
        double bound_include = calculateBound(nextWeight, nextValue, index + 1, W, items);

        // **TỈA CÀNH (PRUNING)**: Nếu cận trên của nhánh này còn THẤP HƠN hoặc bằng giá trị tối đa
        // đã tìm được cho đến nay, thì không cần khám phá sâu hơn nhánh này.
        // Sử dụng epsilon nhỏ khi so sánh double với int để tránh sai số dấu phẩy động
        if (bound_include > max_value - 1e-9) { // bound_include > max_value (cho bài Maximize)
             // Nếu tiềm năng (cận) của nhánh này tốt hơn giải pháp tốt nhất đã biết, thì đi tiếp
            knapsackUtil(index + 1, nextWeight, nextValue, W, items, max_value);
        }
    }


    // ------ Lựa chọn 2: Không bao gồm món đồ items[index] vào túi ------
    // Tính cận trên cho nhánh KHÔNG bao gồm items[index]
    // Cận này dựa trên trạng thái hiện tại và các món đồ còn lại từ index+1
    double bound_exclude = calculateBound(currentWeight, currentValue, index + 1, W, items);

    // **TỈA CÀNH (PRUNING)**: Nếu cận trên của nhánh này còn THẤP HƠN hoặc bằng giá trị tối đa
    // đã tìm được cho đến nay, thì không cần khám phá sâu hơn nhánh này.
    if (bound_exclude > max_value - 1e-9) { // bound_exclude > max_value
        // Nếu tiềm năng (cận) của nhánh này tốt hơn giải pháp tốt nhất đã biết, thì đi tiếp
       knapsackUtil(index + 1, currentWeight, currentValue, W, items, max_value);
    }

    // Lưu ý: Không cần "backtrack" trạng thái (như pop_back trong Subset Sum)
    // vì currentWeight và currentValue được truyền theo giá trị vào lời gọi đệ quy mới.
    // Việc "không đi vào" một nhánh nào đó chính là hành động pruning dựa trên cận.
}


// Hàm chính giải bài toán Knapsack bằng Branch and Bound
int solveKnapsack(int W, std::vector<Item>& items) {
    // Bước 1: Sắp xếp các món đồ theo tỉ lệ giá trị/trọng lượng giảm dần
    // Việc này giúp calculateBound tính cận "chặt" hơn và pruning hiệu quả hơn.
    for(size_t i = 0; i < items.size(); ++i) {
        items[i].ratio = static_cast<double>(items[i].value) / items[i].weight;
    }
    std::sort(items.begin(), items.end(), compareItems);

    int max_value = 0; // Lưu trữ giá trị tối đa tìm được (khởi tạo bằng 0)

    // Bắt đầu quá trình tìm kiếm từ món đồ đầu tiên (index 0),
    // túi rỗng (currentWeight=0, currentValue=0)
    knapsackUtil(0, 0, 0, W, items, max_value);

    return max_value;
}

int main() {
    std::vector<Item> items = {
        {10, 60, 0}, // Trọng lượng, Giá trị, (Ratio sẽ tính sau)
        {20, 100, 0},
        {30, 120, 0}
    };
    int W = 50; // Sức chứa tối đa của túi

    std::cout << "---------- Bai toan 0/1 Knapsack (Optimization) ----------" << std::endl;
    std::cout << "Cac mon do: { (10kg, 60$), (20kg, 100$), (30kg, 120$) }" << std::endl;
    std::cout << "Suc chua tui: " << W << " kg" << std::endl;

    int max_val = solveKnapsack(W, items);

    std::cout << "Gia tri toi da co the mang duoc: " << max_val << "$" << std::endl; // Kết quả nên là 220$ (chọn item 10kg và 20kg)

    return 0;
}

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

// Hàm kiểm tra số nguyên tố
bool isPrime(int n) {
    if (n <= 1) return false;
    for (int i = 2; i * i <= n; ++i) {
        if (n % i == 0) return false;
    }
    return true;
}

// Hướng dẫn giải bằng C++ sử dụng Quay lui (Backtracking) kết hợp Nhánh cận
// Không cung cấp code hoàn chỉnh, chỉ mô tả logic.

void solve() {
    int N, P, S;
    std::cin >> N >> P >> S;

    // 1. Chuẩn bị danh sách các số nguyên tố có thể sử dụng:
    //    - Cần các số nguyên tố lớn hơn P.
    //    - Tổng S không quá lớn (200), nên các số nguyên tố cũng không vượt quá S.
    //    - Ta có thể sàng các số nguyên tố lên đến S hoặc lớn hơn một chút (ví dụ 200).
    //    - Tạo một vector (ví dụ `availablePrimes`) chứa các số nguyên tố p' sao cho P < p' <= S.
    std::vector<int> availablePrimes;
    // Code để sàng và điền vào availablePrimes...
    // Vòng lặp từ P + 1 đến S (hoặc 200), kiểm tra isPrime, nếu là prime thì thêm vào availablePrimes.
    // Ví dụ: for (int i = P + 1; i <= 200; ++i) { if (isPrime(i)) availablePrimes.push_back(i); }
    // Lưu ý: Giới hạn S=200, nên sàng đến 200 là đủ.

    // 2. Khởi tạo cấu trúc lưu kết quả:
    //    - Một vector các vector số nguyên (ví dụ `results`) để lưu các tổ hợp tìm được.
    //    - Một vector số nguyên (ví dụ `currentCombination`) để lưu tổ hợp đang xây dựng.
    std::vector<std::vector<int>> results;
    std::vector<int> currentCombination;

    // 3. Xây dựng hàm quay lui (backtracking function):
    //    - Hàm này sẽ thử thêm các số nguyên tố từ `availablePrimes` vào `currentCombination`.
    //    - Các tham số cần thiết:
    //      - `index`: Chỉ số trong `availablePrimes` mà ta đang xét (để tránh trùng lặp và đảm bảo thứ tự tăng dần).
    //      - `currentSum`: Tổng hiện tại của các số trong `currentCombination`.
    //      - `countChosen`: Số lượng số đã chọn trong `currentCombination`.
    //      - Các tham chiếu đến `availablePrimes`, `results`, `currentCombination`, N, S.

    // void backtrack(int index, int currentSum, int countChosen,
    //                  const std::vector<int>& availablePrimes,
    //                  std::vector<std::vector<int>>& results,
    //                  std::vector<int>& currentCombination,
    //                  int N, int S)
    // {
        // 4. Điều kiện dừng (Base cases):
        //    - Nếu `currentSum == S` và `countChosen == N`:
        //      - Ta đã tìm được một tổ hợp hợp lệ.
        //      - Thêm `currentCombination` vào `results`.
        //      - Kết thúc nhánh này (`return`).
        //    - Nếu `currentSum > S`:
        //      - Tổng đã vượt quá S, nhánh này không hợp lệ.
        //      - Kết thúc nhánh này (`return`).
        //    - Nếu `countChosen > N`:
        //      - Đã chọn quá N số, nhánh này không hợp lệ.
        //      - Kết thúc nhánh này (`return`).

        // 5. Nhánh cận (Pruning):
        //    - Nếu số lượng số còn lại trong `availablePrimes` từ `index` trở đi cộng với số đã chọn (`countChosen`)
        //      ít hơn N, thì không thể chọn đủ N số nữa. Dừng vòng lặp hoặc kết thúc nhánh.
        //    - If (availablePrimes.size() - index + countChosen < N) { return; } // Hoặc break trong vòng lặp

        // 6. Bước đệ quy (Recursive step):
        //    - Duyệt qua các số nguyên tố trong `availablePrimes` từ vị trí `index` trở đi (ví dụ dùng vòng for từ `i = index` đến cuối `availablePrimes`).
        //    - Với mỗi số nguyên tố `p = availablePrimes[i]`:
        //      - Kiểm tra nhánh cận: Nếu `currentSum + p > S`, thì các số tiếp theo trong `availablePrimes` (lớn hơn p) cũng sẽ làm tổng vượt S. Do đó, ta có thể dừng vòng lặp tại đây (`break`).
        //      - Thêm `p` vào `currentCombination`.
        //      - Gọi đệ quy: `backtrack(i + 1, currentSum + p, countChosen + 1, availablePrimes, results, currentCombination, N, S)`.
        //        - `i + 1` đảm bảo số tiếp theo được chọn lớn hơn `p`, tạo ra các tổ hợp khác nhau và đảm bảo thứ tự từ điển.
        //      - Quay lui: Xóa `p` khỏi `currentCombination` (để thử các số khác ở vị trí hiện tại).
        //        - `currentCombination.pop_back();`

    // } // Kết thúc định nghĩa hàm backtrack

    // 7. Gọi hàm quay lui ban đầu:
    //    - Bắt đầu từ chỉ số 0 trong `availablePrimes`, tổng 0, và số lượng đã chọn 0.
    // backtrack(0, 0, 0, availablePrimes, results, currentCombination, N, S);

    // 8. In kết quả:
    //    - In ra số lượng kết quả tìm được (`results.size()`).
    //    - Duyệt qua vector `results` và in từng tổ hợp trên một dòng, cách nhau bởi dấu cách.
    //    - Các kết quả đã được sắp xếp theo thứ tự từ điển do cách duyệt và chọn số nguyên tố tăng dần.
    // Code để in results...

}

// Hàm main chỉ cần đọc T và gọi hàm solve() T lần.
int main() {
    // Tối ưu nhập xuất
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int T;
    std::cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}