Chia tải hai cụm

Bối cảnh và bài toán

Có n gói tác vụ với chi phí xử lý đã biết. Mỗi gói phải được giao cho một trong hai cụm máy chủ. Mục tiêu là làm tổng tải hai cụm chênh lệch ít nhất có thể.

Yêu cầu

Tìm độ chênh lệch nhỏ nhất giữa tổng tải của hai cụm.

Input

• Dòng 1: n.
• Dòng 2: n trọng số p[i].

Output

In độ chênh lệch nhỏ nhất.

Ràng buộc

• 1 <= n <= 20
• 1 <= p[i] <= 10^9

Chấm điểm

Ví dụ 1

Input

5
3 2 7 4 1

Output

1

Giải thích. Có thể chia thành tổng 9 và 8.

Ví dụ 2

Input

2
1 10

Output

9

Giải thích. Mỗi nhóm phải nhận một tập con; phương án tốt nhất có tổng 1 và 10.

Thông tin bài tập

Nguồn: Phỏng theo CSES Problem Set — Apple Division (Task 1623).

Tham khảo: https://cses.fi/problemset/task/1623