Đề bài:

Cho \(n\) gói kẹo \((n\ \leq \ 100)\). Gói thứ \(i\) có \(a_{i}\) viên kẹo. Cần chia các gói kẹo này cho 2 em bé sao cho tổng số viên kẹo mỗi em nhận được chênh lệch ít nhất. Mỗi em nhận nguyên gói. Không mở gói kẹo ra để chia lại.

Dữ liệu vào:

+ Dòng dầu tiên ghi số nguyên dương \(n\)

+ Dòng thứ 2 ghi \(n\) số nguyên lần lượt là \(a_{1},a_{2},\ldots,a_{n}\ (1 \leq a_{i} \leq 100)\)

Kết quả: Một số nguyên duy nhất là số kẹo chênh lệch ít nhất của hai em bé

Ví dụ:

Solution:

Đây thực chất là bài toán ba lô 1 với khối lượng tối đa mà ba lô chứa được là \(s/2\) với \(s\) là tổng số kẹo.