Cần giúp đỡ về code

heoconranbanh_civ · #1 25-11-2019, 23:59

Chào các bác, em thì dân tài chính thôi, nhưng giờ các bác cũng biết là ngành nào cũng có sự trợ giúp của CNTT, do vậy e có cái này cần hỏi các bác, sẽ có hậu tạ nhé

( bác nào code trên java giùm em ạ, vì em dùng mỗi java)

Cho số N và dãy số a1,a2,,,, an ( an hữu hạn ). Viết code để tìm sự khả thi của việc liệu N có bằng tổng của 1 hoặc nhiều các số hạng ghép từ dãy a hay ko.

Em diễn đạt hơi lủng củng nhưng chi tiết các bác có thể xem ở link sau
Finding all possible combinations of numbers to reach a given sum
https://stackoverflow.com/questions/...v3K9_oFYSyyodA

vấn đề ở đây của em là nếu như chạy theo code ở link trên thì sẽ khiến cho nó rất nặng, do vậy giải pháp em đưa ra thì sẽ chạy liệu tổng đó có khả thi hay không rồi mới tìm các bộ số để ghép thành tổng thì chắc là sẽ nhẹ hơn, em hỏi về thuật toán thi đc gợi ý về chạy đệ quy có nhớ ( đệ quy kết hợp quy hoạch động thì sẽ nhẹ hơn)

Một câu hỏi khác nữa thì data input vào ở dạng excel (xlsx) output cũng ở dạng excel (xlsx) thì ngoài thư viện e search trên mạng thì có cách nào giúp nó nhẹ hơn ko nhỉ, vì data input có khi đạt tới số dòng max của excel là tới 1 triệu dòng, hiện em đang phải làm cách chia nhỏ file ra để put vào rồi ra lại ghép lại

Cách e chạy có khả thi hay ko cũng chỉ là 1 phần để làm cho code nó tối ưu hơn vì nếu chạy theo code ở link em đưa thì có vẻ nó chạy tới tết

tthixk · #2 02-12-2019, 22:16

Ý kiến cá nhân:
Bài này đệ quy bình thường, có gì đâu mà tới tết. Độ phức tạp On2 thôi mà.
Quy hoạch động để tìm yes - no theo mình cũng tốn On2, ko khả thi.

Up cho pro thuật toán vào giải.

Bài xlsx có thể unzip và đọc xml.

.gears · #3 02-12-2019, 23:34

1 triệu dòng? nghĩa là một triệu số à thớt? nghĩa là 1 <= N <= 10^6?

nếu tổng toàn bộ dãy A lại nhỏ thì thấy khả thi, còn không thì không có bộ nhớ nào chưa nổi để qui hoạch động cả

1417824

.gears · #4 02-12-2019, 23:39

Quote:

Originally Posted by tthixk

Ý kiến cá nhân:
Bài này đệ quy bình thường, có gì đâu mà tới tết. Độ phức tạp On2 thôi mà.
Quy hoạch động để tìm yes - no theo mình cũng tốn On2, ko khả thi.

Up cho pro thuật toán vào giải.

Bài xlsx có thể unzip và đọc xml.

đệ qui chạy bình thường là O(2^n) nhé, phải duyệt sang toàn bộ tập con

qui hoạch động thì giảm xuống là O(Nn), và bộ nhớ là O(N), nên phụ thuộc vào cái này nữa, nếu nó nhỏ thì không sao. 1417824

conmoedethuong · #5 08-12-2019, 02:58

Tìm sự khả thi hay tìm ra cái dãy đó luôn?
Bài toán này có vẻ khá lạ