30/09/2018, 18:18
Hỏi về giải thuật bài toán tổ hợp
Mình có bài toán như sau: Cho tập gồm 4 chữ số 0, 1, 2, 5. Với hai số k và N cho trước, hãy tìm số các số có k chữ số chỉ gồm 4 chữ số trên, sao cho tổng các chữ số là N.
Ví dụ, với k=3 và N=5, danh sách các số là: 500, 221, 212, 122. Như vậy có tất cả 4 số.
Xin ae chỉ giáo
Bài liên quan
Nếu bạn lập trình nhiều rồi thì chắc đã gặp bài toán
rút tiền trong cây ATM. Bài này cũng na ná như vậy thôi.cám ơn b đã gợi ý. Để mình đi sợt
Với một số bài toán liên quan đến tổ hợp, cách cơ bản mà mình được học là dùng kĩ thuật backtracking để liệt kê. Nâng cao để tối ưu hơn một tí thì có kĩ thuật nhánh cận.
Như bài trên thì điều kiện cho nhánh cận có thể là: khi chọn ra chưa đủ k số mà tổng của nó đã lớn hơn N thì ko cần chọn tiếp.