Hướng dẫn bài BTCANDY - Chia kẹo

Bài này có thể giải bằng Duyệt quay lui hoặc Quy hoạch động.

Cách giải bằng Duyệt quay lui:

Mỗi phương án chia kẹo là một véc-tơ , trong đó:

Do đó ta sẽ dùng duyệt quay lui để đếm tất cả các phương án chia kẹo thỏa mãn.

• Thủ tục Backtracking:

/*
+ i: Người sẽ xét để chia kẹo
+ prev: Số kẹo đã chia cho người trước đó
+ remain: Số kẹo còn lại
*/
void BT(int i, int prev, int remain) {
    if (i > n) {
        if (remain == 0)
            dem++;
        return;
    }
    for (int j = prev; j >= 1; j--)
        if (j <= remain)
            BT(i + 1, j, remain - j);
}

Trong chương trình chính ta khởi tạo biến dem = 0 và gọi BT(1, M, M);

• Để in ra một phương án chia kẹo theo yêu cầu:
  • Đem số kẹo M chia đều cho N người, mỗi người được cái kẹo
  • Lấy số dư chia cho người đứng đầu, mỗi người một cái.