Bài toán chia kẹo

Bài toán chia kẹo là một dạng toán điển hình, bài toán này có phương pháp giải đặc biệt, tư tưởng của nó có thể được áp dụng để giải cho rất nhiều bài toán khác trong Tin học . Nó còn có tên gọi là Number Partitioning, không có thuật toán tối ưu để giải. Sau đây là những thuật toán từ đơn giản đến khó để giải quyết bài tập này .

Nhắc lại bài toán chia kẹo

Có N gói kẹo, gói thứ i có Aicái kẹo. Không được bóc bất kỳ một gói kẹo nào, cần chia N gói kẹo thành hai phần sao cho độ chênh lệch số kẹo giữa hai gói là ít nhất.

Dữ liệu vào trong file “chiakeo.inp” có dạng :

- Dòng đầu tiên là số N(N<=100);

- Dòng thứ hai là N số Ai(i=1, 2,.., N; Ai <=100).

Kết quả ra file “chiakeo.out” có dạng:

- Dòng đầu là độ chênh lệch nhỏ nhất giữa hai phần có thể được.

- 2 dòng tiếp theo là 2 đoạn đã được chia ra sao cho chênh lệch là ít nhất

Thuật toán

1./ Vét cạn

Thuật toán vét cạn dễ hiểu nhất là xét tất cả các tập con có thể và tính tổng tập con sao cho chênh lệch nhỏ nhất với sum/2 ( sum là tổng giá trị của các phần từ a[i] ).Ưu điểm : Dễ hiểu, tính chính xác cao Nhược điểm : Độ phức tạp lớn O(2^n). Sẽ không khả thi nếu n là một số lớn.

2./ Tham lam

Thuật toán này cũng rất dễ hiểu, đó là sắp xếp lại mảng giảm dần , đưa 2 số lớn nhất vào 2 mảng, tiếp tục thêm số tiếp theo vào mảng có tổng bé hơn cho đến khi không còn số để đưa

Ví dụINPUT 56 3 4 8 1Đầu tiên sắp xếp lại mảng A ta được A(8,6,4,3,1)Đưa 2 số lớn nhất vào 2 mảng B và C , cụ thể B(8) và C(6)Xét tiếp A[3]=4 và ta nhận thấy mảng C có tổng bé hơn mảng A, ta đưa 4 vào mảng C, mảng C sẽ cập nhật lại là C(6,4)Tiếp tục xét đến A[4]=3, ta nhận thấy mảng B hiện tại có giá trị là 8 và thấp hơn mảng C=10, ta đưa A[4]=3 vào mảng BA[5]=1, ta nhận thấy mảng C thấp hơn mảng B, thêm A[5] vào mảng C Kết thúc chương trình ta có mảng B(8,3) và mảng C(6,4,1) và 2 mảng thỏa điều kiện chênh lệch ít nhất .Ưu điểm : Nhanh gọn, độ phức tạp nhỏ , dễ hiểu.Nhược điểm : Cho ra kết quả không được tốt lắm.

Phương pháp Karmarkar-Karp

Đây là một phương pháp cho kết quả khá tốt nhưng không khó cài đặt lắmĐầu tiên sắp xếp các số theo thứ tự giảm dần ,lấy 2 số lớn nhất và tìm hiệu của chúng , lấy hiệu của chúng và gán vào mảng A đang xét. Ví dụINPUT 67 1 2 5 9 6Sắp xếp mảng A theo thứ tự giảm dần ta có A(9,7,6,5,2,1)Xét 2 số đầu ta có hiệu là 2, đưa hiệu đó vào mảng ta được A(6,5,2,1,2)Tiếp tục lấy hiệu 2 số đầu và đưa vào cuối mảng ta được A(2,1,2,1)=>A(2,1,1)=>A(1,1)=>A(0), kết thúc chương trình khi mảng A còn 1 phần tử , và đó là độ chênh lệch nhỏ nhất giữa 2 đoạn.Ưu điểm : Cho ra kết quả tốt hơn phương pháp tham lam.Nhược điểm : Đây không phải là một thuật toán tối ưu, kết quả là độ chênh lệch , còn về việc in ra 2 đoạn con thì cần phải thiết lập thêm.

4./ Quy hoạch động

Gọi T là tổng các gói kẹo có được, chúng ta cần tìm dãy con có tổng bằng S sao cho T-2S là nhỏ nhất. Khi ta tìm được các phần tử của S sẽ là phần kẹo thứ nhất, phần kẹo thứ 2 sẽ là các phần tử còn lại Xét tất cả các gói kẹo để chọn ra gói kẹo j bé nhất thỏa mãn i ≥ A[j] và F[i-A[j]] ≤ j. Nếu F[i] = +∞ thì không chọn được. Nếu F[i] ≠ +∞ thì truy vết từ mảng F tìm ra chỉ số các gói kẹo cần chọn. Ưu điểm : Thuật toán này tối ưu nhất trong tất cả các cách trên.Nhược điểm : Khó hiểu cho các bạn mới tập làm quen với lập trình .

Code tham khảo áp dụng quy hoạch động tại đây