Dùng thuật quay lui để tìm cách chia tiền hợp lý cho 2 người

minhcanhtu · September 15, 2018, 4:16pm

Chào mọi người. Mình có đang giải 1 problem sau: http://ntucoder.net/Problem/Details/4420
Ý tưởng của mình là dùng quay lui sinh dãy nhị phân, quy ước: 0 là của bạn A và 1 là của bạn B.
Độ dài dãy nhị phân được sinh ra là n. Sau khi sinh ra xong, ta sẽ kiểm tra nếu số tiền mà A nhận được = số tiền mà B nhận được thì thêm dãy kết quả vào một vector<string>.
Mình cài đặt thuật toán như sau: https://ideone.com/F3D4PP

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

using namespace std;

int arr[20], nofs = 0;

void gen(const vector<int> &mvc, vector<string> &res, int n, int i = 0)
{
    if (i == n) {
        int a, b;
        string s;
        int sumofa = 0, sumofb = 0;
        for(int j = 0; j < n; ++j) {
            if (arr[j] == 0) {
                s.push_back('A');
                sumofa += mvc[i];
            }
            else {
                s.push_back('B');
                sumofb += mvc[i];
            }
        }
        if (sumofa == sumofb) {
            res.push_back(s);
            ++nofs;
        }
    }
    else {
        arr[i] = 0;
        gen(mvc, res, n, i + 1);
        arr[i] = 1;
        gen(mvc, res, n, i + 1);
    }
}

int main()
{
    int n;
    vector<int> mvc; // store input sequence
    vector<string> res; // store result
    cin >> n;
    mvc.resize(n);
    res.resize(n);
    for (int i = 0; i < n; ++i) {
        res[i].resize(n);
        cin >> mvc[i];
    }
    gen(mvc, res, n);
    if (nofs > 0) {
        cout << nofs << endl;
        for (int i = 0; i < nofs; ++i) {
            for (int j = 0; j < n; ++j) {
                cout << res[i][j] << " ";
            }
            cout << endl;
        }
    }
    else cout << "khong chia duoc";
    return 0;
}

và chạy thử với input mẫu: 6 1 2 2 5 10 10
thì output sai hoàn toàn. (như stdout ở link IDEone trên)
Mình mò mãi vẫn ko biết lỗi ở chỗ nào, Codeblocks thì đặt break point ở dòng đầu tiên hàm main() thì ko debug được!
Nhờ mọi người giúp đỡ mình xem sai ở chỗ nào và cách sửa, cách cải thiện ra sao ạ !
Xin cảm ơn.

tntxtnt · September 16, 2018, 12:00am

minhcanhtu:

        for(int j = 0; j < n; ++j) {
            if (arr[j] == 0) {
                s.push_back('A');
                sumofa += mvc[i];
            }
            else {
                s.push_back('B');
                sumofb += mvc[i];
            }
        }

trong vòng for của j mà đi cộng [i]?

res là cái gì sao đi resize tá lả thế kia?

minhcanhtu · September 15, 2018, 11:56pm

Em nhầm mất, đã sửa thành mvc[j].

Hmm, res là vector string để lưu ma trận các ký tự A và B rồi một hồi cout ra theo đúng output mẫu của đề bài. Em thấy trong hàm gen mình dùng push_back cho res thì chắc bỏ dòng resize trong vòng for kia đi, nhưng khi in ra thì chỉ ra được số cách chia tiền (biến nofs) chứ nó lại ko ra ma trận anh?

Edit: À, em thử sửa lại dòng res.push_back(s) thành res[ind++] += s thì đã in ra được. (ind là biến toàn cục được set value ban đầu = 0). Cho em hỏi sự khác nhau giữa 2 dòng lệnh đó được ko ạ?

minhcanhtu · September 16, 2018, 12:00am

OK, vậy là em bị nhầm ở chỗ resize cho vector res rồi. Đêm khuya ko tỉnh táo code tầm bậy quá ^^
Fixed AC code:

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

using namespace std;

int arr[20], nofs = 0, ind = 0;

void gen(const vector<int> &mvc, vector<string> &res, int n, int i = 0)
{
    if (i == n) {
        int a, b;
        string s;
        int sumofa = 0, sumofb = 0;
        for(int j = 0; j < n; ++j) {
            if (arr[j] == 0) {
                s.push_back('A');
                sumofa += mvc[j];
            }
            else {
                s.push_back('B');
                sumofb += mvc[j];
            }
        }
        if (sumofa == sumofb) {
            res.push_back(s);
            ++nofs;
        }
    }
    else {
        arr[i] = 0;
        gen(mvc, res, n, i + 1);
        arr[i] = 1;
        gen(mvc, res, n, i + 1);
    }
}

int main()
{
    int n;
    vector<int> mvc; // store input sequence
    vector<string> res; // store result
    cin >> n;
    mvc.resize(n);
    for (int i = 0; i < n; ++i) {
        cin >> mvc[i];
    }
    gen(mvc, res, n);
    if (nofs > 0) {
        cout << nofs << endl;
        for (int i = 0; i < nofs; ++i) {
            for (int j = 0; j < n; ++j) {
                cout << res[i][j] << " ";
            }
            cout << endl;
        }
    }
    else cout << "khong chia duoc";
    return 0;
}

tntxtnt · September 16, 2018, 12:48am

chém gió vậy đc hem

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

bool canSplitEvenly(const std::vector<unsigned>& bills, unsigned config)
{
    return 2 * std::accumulate(rbegin(bills), rend(bills), 0u,
        [&](unsigned total, unsigned bill) {
            total += config % 2 * bill;
            config >>= 1;
            return total;
        }) == std::accumulate(begin(bills), end(bills), 0u);
}

void printConfig(unsigned config, unsigned n)
{
    for (unsigned mask = 1u << n; mask >>= 1; )
        std::cout << "BA"[bool(config & mask)] << " ";
    std::cout << "\n";
}

int main()
{
    unsigned n; std::cin >> n;
    std::vector<unsigned> bills(n);
    for (auto& bill : bills) std::cin >> bill;
    
    std::vector<unsigned> validConfigs;
    for (unsigned config = 1u << n; config--; )
        if (canSplitEvenly(bills, config))
            validConfigs.push_back(config);
        
    if (validConfigs.empty())
        std::cout << "Khong chia duoc\n";
    else
        std::cout << validConfigs.size() << "\n";
    for (auto config : validConfigs)
        printConfig(config, n);
}

minhcanhtu · September 16, 2018, 1:29am

Kinh khủng quá
Em toàn dành thời gian tập trung vào thuật toán chứ ít khi practice về CTDL