Một ứng dụng của toán học và thuật toán!

Một ứng dụng của toán học và thuật toán!

Xin các pác giúp thêm cho em một bài toán nhỏ này nhưng có trong thực tế.

Bài toán này được hình thành sau khi có một kế toán trưởng kiểm tra lại doanh thu trong tháng của cửa hàng.

Theo danh mục, cửa hàng kinh doanh 28 mặt hàng. Do không thạo Excel nên người nhân viên cửa hàng đã dùng máy tính tay để cộng tất cả doanh thu trong tháng, mặc dù số liệu đã được nhập vào Excel. Thế nhưng, do không cẩn thận, anh ta đã bỏ sót một số mục.
Sau đó, kế toán trưởng kiểm tra và phát hiện ra lỗi. Nhưng chỉ trong một buổi chiều, anh ta và người nhân viên không thể phát hiện ra được những danh mục đã không được cộng.

Các pác có thể giúp em giải bài toán này được không (chỉ ra những mục chưa cộng). Nhưng xin lưu ý là nếu số mặt hàng kinh doanh của cửa hàng đó lớn hơn thì giải quyết bài toán như thế nào là hợp lý.

Các pác có thể cung cấp cho iem thuật toán cũng được!
Xin cảm ơn!


Đọc và viết!

Bài này nếu tổng quát lên sẽ là bài toán rất khó. NP- complete. Không (chưa) có thuật toán nhanh. Chỉ có thuật toán xấp xỉ...
Còn với n=28 thi chắc chắn là giải được, cùng lắm là sét 2^28 khả năng.
Có một cách chắc là người ra đề nghĩ tới đó là "dinamic prorgamming" đại loại là cho biến số dư là c, sau đó cứ cho c tăng dần , vừa tăng c vừa tìm, những mục mà anh kia bỏ sót, khi c tăng tới giá trị cần tìm là được.
Tuy nhiên nếu tớ mà là anh kia, tớ sẽ làm lại từ đầu, nhất là mọi thứ đã ở trong exel, chỉ cần SUM một cái là xong!!!
Matek

Chuyện không phải đơn giản như thế đâu bác Matex ạ! Ban đầu tui cũng định kể nốt câu chuyện, nhưng thấy nó dài quá! Hôm nay, bác nói thế thì em xin kể nốt.
Trước khi phát hiện ra lỗi, anh kế toán trưởng đã bổ sung thêm một vài danh mục hàng đã bán trong tháng (sử dụng chính file do anh nhân viên tạo ra), đồng thời thay đổi doanh thu của một số danh mục hàng mà người nhân viên kia đã làm. Làm xong, anh ta mới phát hiện ra sự nhầm lẫn của anh nhân viên khi so sánh hai bản in, một của anh ta và một của người nhân viên đó. Và cũng vào lúc đó, anh ta không nhớ được mình đã sửa mục nào, bởi vì các số đều là con số mang tính chất "báo cáo" (chuyện thực của một số nhân viên kế toán - miễn sao cho hợp thức hoá khoản thu chi) và các con số đều là "tự nghĩ trong đầu mà ra" hay còn gọi là "vỗ bụng". Thế cho nên, xếp của anh ta yêu cầu phải tìm ra các danh mục đã không được cộng ban đầu.
Chuyện hơi khó tin nhưng đó là một bài toán có mô hình rất thực. Và nếu tổng quát hoá lên thì liệu có phương pháp nào thực thi hay không?
Dù sao cũng cảm ơn pác Matek!
Tui cũng đã dùng pascal trong 1h15p và đã tìm ra được 3 bộ số (có ít nhất là 07 danh mục) mà anh nhân viên chưa cộng, nhưng sai số của bộ số đó so với tổng thực (chính xác) vẫn là trên 100 đồng. Giá trị này không cho phép trong thuật toán vì yêu cầu của chúng ta là phải tìm ra bộ số đúng. Trong bài toán thực tế ban đầu, nếu anh nhân viên bấm nhầm máy tính thì mọi chuyện trở nên công cốc. Nhưng khi đưa vào mô hình toán thì chúng ta giả thiết là tất cả các con số mà anh nhân viên đã cộng là chính xác.
Rất mong các pác tiếp tục giúp đỡ!
Cố gắng đưa lý thuyết vào thực tế!

Bác thử mô hình lại bài toán cái, bác cho em những gì và bác đòi hỏi em những gì... Chứ đọc thế này em confused quá!!!
I believe in angels, something good in everything I see...

Ok!
Cho n số thực, gồm t1, t2, t3, ..., tn-1 và tn. Cộng m số lại với nhau (m < n, m không biết trước) được kết quả là S.
Tìm m và bộ số đã được cộng trong tổng S.

theo em nghĩ, với bài toán kiểu này thì chẳng có thuật toán nào có thể gọi là thông minh để giải quyết được, trừ thuật toán ... vét cạn
vét khéo khéo 1 chút, với số lượng phần tử vừa phải (n<100), với số lượng phần tử bị thiếu (n-m) không lớn lắm, thì cũng không mất nhiều thời gian lắm để vét đâu

Nếu các số liệu là nguyên (hoặc thực với 2,3 số sau dấu phẩy) và tổng của chúng ko quá lớn thì bài này hoàn toàn có thể giải được bằng QHĐ, nếu ko thì ko có cách nào khác ngoài duyệt có cận đâu.
I believe in angels, something good in everything I see...

Các pác ơi, vấn đề là thuật toán cụ thể như thế nào để máy tính còn có thể giải quyết được. Nếu thuật toán không "ngon" là máy tính chạy từ sáng tới chiều mà không ra được là mệt lắm!
Sáng chạy, trưa chạy, chiều vẫn ... còn chạy!

Đây có lẽ là bài toán tối ưu hóa tuyến tính LP hệ số nguyên (Integer Linear Programming hoặc Mixed Integer Linear Programming), trường hợp đặc biệt của bài toán tuyến tính LP (Linear Programming)
minimize   cxThỏa mãn điều kiện Ax  = b, x >= 0Trong đó A là ma trận hệ số cho trước.
--------------------
Bạn tìm trên mạng Internet sẽ thấy nhiều lắm. Chỉ cần tra google với từ khóa là "Integer Linear Programming" hoặc "Mixed Integer Linear Programming" là được. Có nhiều chương trình hoặc thư viện được người ta viết sẵn rồi, có cả DEMO. Các bạn chịu khó thử và "may đo" cho hợp của mình là được.
Trong bài toán nêu trên, bài toán LP sẽ là như sau:
x1 * t1 + x2 * t2 + .... + xn * tn = S
x1 <= 1
x2 <= 1
...
xn <= 1
xi là số nguyên, xi>=0
ti, S là các hệ số cho trước.
Tìm max của M=x1 * 1 + x2 * 1 + ... + xn * 1
max của M chính là giá trị m lớn nhất có thể tìm được. Còn nếu bạn muốn tìm m theo ý muốn, ví dụ m nhỏ hơn giá trị m0 cho trước thì có thể thêm ràng buộc x1+...+xn<=m0.
Thuật giải là dùng thuật toán Simplex để giải bài toán LP với xi là số thực. Sau đó kết hợp với phương pháp chia để trị để tìm nghiệm xi nguyên. Với ma trận A 200x200 (hay số lượng mặt hàng lên đến 200 mặt hàng), có thể phải chạy đến 10 phút. (không nhiều đến 2^28 khả năng đâu)
---------------------
Khi sử dụng các thư viện (lib) trên Internet chuyên giải bài toán MILP, các bạn nên chọn thư viện nào có chương trình demo và hướng dẫn sử dụng đi kèm. Cũng phải đầu tư một ít thời gian để đọc hiểu nguyên lý giải bài toán MILP trước khi sử dụng thư viện.
VaViu-MeoMeo-AK47-Toi yeu mau trang nho nho, nhac dam dut, noi buon khong ten.

Chào bạn,
Đây là (trường hợp riêng) của bài tóan MAXIMUM KNAPSACK, NP-Complete. Thuật tóan xấp xỉ hiệu quả đăng ở đây:
Gens, G. V., and Levner, E. V. (1979),
``Computational complexity of approximation algorithms for combinatorial problems'',
Proc. 8th International Symp. on Mathematical Foundations of Comput. Sci., Lecture Notes in Comput. Sci. 74, Springer-Verlag, 292-300
và ở đây:
Ibarra, O. H., and Kim, C. E. (1975),
``Fast approximation for the knapsack and sum of subset problems'',
J. ACM 22, 463-468.

Altus