[12/04/2020 03:08] [Hỏi đáp] Em đang giải 1 bài toán nhưng gặp phải . . .


#1

Nguồn post: https://www.facebook.com/257768141347267_1116124712178268
[Hỏi đáp] Em đang giải 1 bài toán nhưng gặp phải khó khăn, mong các anh chị/bạn cho em xin gợi ý ạ. Bài toán cụ thể như sau: Cho M trái táo bỏ vào N giỏ (M>N), sẽ thu được 1 array (như array dưới phần tô màu vàng). Với điều kiện là không giỏ nào lớn hơn 3, và mỗi giỏ ít nhất 1 quả. Hãy viết function để xuất ra được 1 array tương ứng với tham số M, N. Em có ví dụ vài kết quả trong hình, em không biết nên code thế nào, bài này có tên thuật toán hay gì k ạ, em xin cảm ơn!


#2

Câu hỏi cụ thể là gì thế bạn?


#3

Có thể coi đây là bài toán liệt các cách tách số M thành tổng của N số nhỏ hơn, nằm trong khoảng 1-3. Bạn tham khảo quyển Giải thuật và Lập trình của thầy Lê Minh Hoàng, phần các bài toán liệt kê tổ hợp, chỉnh hợp có vài bài tương tự như này, nhưng bạn cần thêm bớt 1 vài điều kiện cho phù hợp với bài toán của bạn.


#4

backtracking thử xem


#5

Nếu M, N ko quá to có thể dùng loop over itertools.combinations_with_replacement([1,2,3], N), check tổng bằng M rồi in ra


#6

Từ khóa bạn nên tìm hiểu là “Constraint Programming”.


#7

Tổ hợp chập n của m, với n<m


#8

Bạn giới hạn tổng táo M< N tổng giỏ và tổng táo M<=3xN giỏ do số táo mỗi giỏ không quá 3 để kiểm tra data input. Dùng vòng lặp in range [1,3] add táo vào aray, và in ra kết quả.


#9

Cách dễ nhất là dùng backtracking như bạn ở trên có nói. Code minh họa cho em luôn này: https://repl.it/join/tmwjpkbz-hieutran106