Hỏi Về Cách Duyệt Tổ Hợp - Programming - Dạy Nhau Học Trang chủ » Duyệt Tổ Hợp » Hỏi Về Cách Duyệt Tổ Hợp - Programming - Dạy Nhau Học Có thể bạn quan tâm Duyệt Trâu Duyet Trinh Duyet Trinh Coc Coc Duyệt Trình Internet Explorer Duyệt Trình Web Hỏi về cách duyệt tổ hợp programming c++ gothammmmm (crackker) July 10, 2021, 2:42am #1 Em có 1 đề bài dạng như thế này: “Cho m con đường, chọn k con đường sao cho thoả mãn nhất…” Trước khi nghĩ thuật chuẩn thì em đang định làm trâu cho subtask m <= 32 và k <= 7. Em thấy là nếu chọn k cái bất kì trong m cái thì cần mCk trường hợp thì chỉ tầm 3 triệu là ok rồi nên em đang nghĩ đến việc đệ quy rồi check nhưng có vẻ như nó quá thời gian khi em nộp, code em có dạng tựa tựa thế này: void backtrack() { if(p.size() == k) { ll res = cal() ; ans = max(ans, res) ; return ; } FOR(i, 1, m) { if(dd[i]) continue ; p.pb(i) ; dd[i] = 1 ; backtrack() ; p.pop_back() ; dd[i] = 0 ; } } void solve() { FOR(i, 1, m) { p.pb(i) ; dd[i] = 1 ; backtrack() ; p.pop_back() ; dd[i] = 0 ; } cout << ans << ' ' ; } Cho em hỏi vì sao trâu đệ quy lại quá thời gian và nên làm thể nào cho chuẩn với subtask này ạ ! tntxtnt () July 10, 2021, 2:32am #2 C++ ko có duyệt từng tổ hợp nhưng có duyệt tất cả các chỉnh hợp, có thể sửa nó thành duyệt tổ hợp n chập k như sau: #include <iostream> #include <algorithm> #include <vector> #include <string> int main() { // Ví dụ chuỗi "1234567" là mảng chứa n=7 ký tự, duyệt tất cả các tổ hợp với k=4 std::string s = "1234567"; int n = s.size(); int k = 4; std::vector<int> take(n, 0); std::fill(begin(take), begin(take) + k, 1); int id = 0; do { std::cout << ++id << ": "; for (int i = 0; i < n; ++i) if (take[i]) std::cout << s[i]; std::cout << "\n"; } while (std::prev_permutation(begin(take), end(take))); } hơi rắc rối tí :V :V Hàm std::next_permutation hay std::prev_permutation cho mảng chứa n phần tử khác nhau đôi một sẽ duyệt n! lần (chỉnh hợp của n phần tử đó). Ví dụ mảng {0,1,2,3} nó sẽ duyệt 4! = 24 lần từ 0123 tới 3210 với next_permutation và từ 3210 về 0123 với prev_permutation. Nếu có m phần tử trùng nhau trong n phần tử thì nó chỉ duyệt \dfrac{n!}{m!} lần (bỏ qua m! lần trùng nhau). Vậy để nó duyệt đúng tổ hợp n chập k = \dfrac{n!}{k!(n-k)!} thì ta cần tạo tập hơn n phần tử với k phần tử giá trị 1 (chọn nên lấy giá trị là 1) và n-k phần tử giá trị 0 (ko chọn): std::vector<int> take(n, 0); // mảng n phần tử 0 std::fill(begin(take), begin(take) + k, 1); // gán 1 cho k phần tử đầu tiên rồi duyệt prev_permutation để nó duyệt từ 11...100...0 về 00...011...1. Cuối cùng để lấy các phần tử trong mảng cần lấy n chập k thì ta ktra nếu take[i] thì s[i] sẽ được chọn. 4 Likes gothammmmm (crackker) July 10, 2021, 3:48am #3 cách này em hiểu rồi nhưng em nghĩ là với số lớn thì next_permutation sẽ mất n! độ phức tạp sẽ quá thời gian ý ạ ? vì subtask ở đây là m <= 32 thì cơ bản việc next_permutation của 32 đã quá thời gian rồi. Em nghĩ next_permutation chỉ hợp với m <= 10, còn với m <= 20 thì sinh nhị phân là ok qua. Nhưng với m <= 32 thì em đang thắc mắc tntxtnt () July 10, 2021, 11:12am #4 m=32 mà k=7 duyệt cách trên cũng được mà :V Nó ko xét 32! trường hợp đâu, chỉ xét khoảng \dfrac{32!}{7! \times 25!} thôi :V a chạy đếm thử C(32, 7) hơn 3tr trường hợp có 0.05s nè tức là nó ko duyệt 32! đâu. Thư viện chuẩn người ta cũng khôn lắm chứ =] image1013×793 30.6 KB 3 Likes gothammmmm (crackker) July 10, 2021, 3:42pm #5 dạ vâng em cảm ơn anh ạ ! <3 DayNhauHoc's Discord Học C++ Free? Click Blog Dạy Nhau Học Tự Học Lập Trình 83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao? Từ khóa » Duyệt Tổ Hợp [PDF] BÀI 3: BÀI TOÁN LIỆT KÊ TỔ HỢP - Topica Liệt Kê Các Hoán Vị Tổ Hợp Sử Dụng Code C++ - Lập Trình Không Khó Thuật Toán Tính Tổ Hợp - Cách Tính Tổ Hợp Trong C++ Bài Toán Liệt Kê Các Tổ Hợp K Của N Phần Tử - Cộng đồng C Việt Thuật Toán Quay Lui (Backtracking) - Viblo Quay Lui Tổ Hợp Chập K Của N Bằng C++ (giải Thích Chi Tiết) - YouTube [ Lập Trình C/C++ ] Quay Lui Liệt Kê Tổ Hợp Chập K Của N - Diễn Đàn 10 Tổ Hợp Phím Tắt Cần Thiết Cho Các Tab Trình Duyệt - .vn Các Thuật Toán Sinh - Quanghuy Phê Duyệt Quy Hoạch Chi Tiết Xây Dựng Dự án Tổ Hợp Sản Xuất Sản ... Toán Học Tổ Hợp – Wikipedia Tiếng Việt Thuật Toán Quay Lui - Chương Trình Sinh Tổ Hợp Cơ Bản. - YouTube
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao? 