Bai toan chia keo. pascal

BÀI TÓAN CHIA KẸO
  Trong số báo THNT tháng 8/2003, chuyên mục Đề ra kỳ này, có bài tóan “Chia kẹo”. Nội dung của bài tóan như sau:
 
Có N gói kẹo, gói thứ i có A[i] cái kẹo.
 
Yêu cầu: Hãy tìm cách chia các gói kẹo này thành 2 phần sao cho độ chênh lệch giữa tổng số kẹo ở hai phần là ít nhất có thể được 0 Dữ liệu vào:
Cho trong file Chiakeo.inp: Một dòng duy nhất gồm các giá trị là số kẹo trong mỗi gói, các số cách nhau bởi một dấu cách (N = số gói kẹo đọc được)
 
Dữ liệu ra:
Ghi ra file Chiakeo.out
-          Dòng 1 lần lượt ghi 3 số: tổng số kẹo ở phần 1, phần 2 và độ chênh lệch giữa hai phần.
-          Dòng 2,3 là giá trị các gói kẹo ở mỗi phần được chia.
 
Dạng bài tóan này xuất hiện nhiều trong các ứng dụng về lập lịch, nó còn có tên gọi là Number Partitioning. Đây là một bài tóan thuộc lớp NP đầy đủ, không có thuật tóan tốt  để giải. Bài viết này xin được trình bày một cách giải Heuristic cho ra kết qủa khá tốt.
 
Ta phát biểu lại bài tóan: cho n số (trong trường hợp này là số nguyên), tìm cách chia thành 2 phần sao cho độ chênh lệch tổng các số của mỗi phần là ít nhất có thể được
 
Trước hết chúng ta hãy xem xét một số cách giải:
1.      Duyệt vét cạn
Thuật tóan vét cạn dễ hiểu nhất là xét tất cả các tập con có thể, và trả về tập con có tổng gần với một nửa tổng các số nhất. Nếu có n số, độ phức tạp của thuật tóan sẽ là O(2n) bởi vì một tập n phần tử có 2n tập con. Không gian tính tóan sẽ là O(n). Như vậy cách tiếp cận này không thực tiễn khi n lớn.
Cũng với tư tưởng duyệt vét cạn, bạn có thể cải tiến thành một thuật tóan có độ phức tạp O(2n/2) nhưng ở đây sẽ không bàn kỹ về vấn đề này.
2.      Quy họach động
Thuật giải quy họach động đòi hỏi một mảng bít a[i] có kích thước là tổng các số, a[i]=1 khi và chỉ khi tồn tại tập con có tổng bằng i. Ban đầu, ta khởi tạo mảng a bằng 0, đặt a[0]=1. Sau đó với mỗi số x , quét lại mảng a, và với mỗi phần tử a[i]=1,  ta đặt a[i+x]=1. Tiếp tục cho đến khi xét hết dãy số. Không gian tính tóan của thuật giải này phụ thuộc vào tổng các số. Do đó, nó chỉ thực tiễn với các số là số nhỏ, và phải là số nguyên.
3.      Tham lam
Thuật giải tham lam dễ thấy nhất cho bài tóan này như sau: sắp xếp các số theo thứ tự giảm, rồi đặt số lớn nhất vào một trong hai tập. Sau đó, đặt số tiếp theo vào tập đang có tổng bé hơn, tiếp tục cho đến khi tất cả các số được xét.
Thuật giải này cài đặt rất nhanh, nhưng thường cho ra kết qủa không được tốt lắm
 
Phương pháp Karmarkar-Karp
Dưới đây, chúng ta xem xét một phương pháp Heuristic cho kết qủa khá tốt và cũng không khó cài đặt lắm.
Phương pháp Karmarkar-Karp (KK) đầu tiên sẽ sắp xếp các số theo thứ tự giảm dần. Tại mỗi bước, thuật tóan sẽ lấy hai số lớn nhất phân vào hai phần khác nhau ; mà chưa cần quan tâm là số nào sẽ đi vào tập nào.  
Cụ thể, thuật tóan sẽ lọai bỏ hai số lớn nhất, lấy hiệu của chúng – xem đó như một số khác và chèn trở lại vào danh sách đã sắp xếp. Thuật tóan sẽ tiếp tục cho đến khi chỉ còn lại 1 số duy nhất, đó chính là giá trị chênh lệch của hai tập.
Ví dụ, ta có dãy (8; 7; 6 ; 5 ;4 )
Bước
Dãy
Hiệu của 2 số lớn nhất

0
(8; 7; 6 ; 5 ; 4)
8 – 7 = 1

1
(6; 5; 4; 1)
6 – 5 = 1

2
(4; 1; 1)
4 – 1 = 3

3
(3; 1)
3 – 1 = 2

4
(2)
 

 
Trong ví dụ này, bạn sẽ thấy phương pháp KK chạy tốt hơn phương pháp tham lam, nhưng vẫn chưa đưa ra được kết qủa tối ưu nhất.
 
Nếu cần in ra nội dung