Chia kẹo

Chia kẹo
Cho n gói kẹo, gói thứ i có ai viên. Hãy chia các gói thành 2 phần sao cho chênh lệch giữa 2 phần là ít nhất.

Hướng dẫn:
 Gọi T là tổng số kẹo của n gói. Chúng ta cần tìm số S lớn nhất thoả mãn: 
• S≤T/2.
• Có một dãy con của dãy a có tổng bằng S.
Khi đó sẽ có cách chia với chênh lệch 2 phần là T–2S là nhỏ nhất và dãy con có tổng bằng S ở trên gồm các phần tử là các gói kẹo thuộc phần thứ nhất. Phần thứ hai là các gói kẹo còn lại.