Chia Hai Nhóm Cân Bằng

Buổi 23 — Thao tác bit Buổi 69-70 — Mock Tổng hợp
Points
45
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề bài

Có $N$ quả táo, quả thứ $i$ có khối lượng $w_i$. Hãy chia $N$ quả táo này thành hai nhóm (có thể một nhóm rỗng) sao cho chênh lệch tuyệt đối giữa tổng khối lượng của hai nhóm là nhỏ nhất có thể.

Dữ liệu vào
  • Dòng đầu tiên chứa số nguyên $N$ ($1 \le N \le 20$).
  • Dòng thứ hai chứa $N$ số nguyên $w_1, w_2, \dots, w_N$ ($1 \le w_i \le 10^9$).
Dữ liệu ra
  • Một số nguyên duy nhất là chênh lệch khối lượng nhỏ nhất.
Ví dụ
Input Output
5
3 2 7 4 1
1
Giới hạn
  • $1 \le N \le 20$
  • $1 \le w_i \le 10^9$
Draft saved