Bài 18.5. Phân Chia Kho Báu Chiến Lợi Phẩm - Độ khó: Khó

Sau một cuộc phiêu lưu thành công, một nhóm thợ săn kho báu đã thu được N viên ngọc quý giá, mỗi viên có một giá trị riêng. Để đảm bảo công bằng và tránh tranh chấp, họ quyết định chia kho báu thành hai phần. Tuy nhiên, họ muốn sự chênh lệch về tổng giá trị giữa hai phần là nhỏ nhất có thể. Bạn được giao nhiệm vụ tính toán giá trị chênh lệch tối thiểu này.

Mô tả bài tập: Cho một mảng A gồm N số nguyên dương, mỗi số đại diện cho giá trị của một viên ngọc. Chia các viên ngọc này thành hai nhóm (không nhất thiết phải có số lượng ngọc bằng nhau trong mỗi nhóm) sao cho tổng giá trị của nhóm thứ nhất và tổng giá trị của nhóm thứ hai có sự chênh lệch tuyệt đối nhỏ nhất. Bạn cần tìm và trả về giá trị chênh lệch tuyệt đối nhỏ nhất này. Mỗi viên ngọc phải thuộc về đúng một nhóm.

INPUT FORMAT

Dòng đầu tiên chứa một số nguyên N (1 <= N <= 20), là số lượng viên ngọc. Dòng thứ hai chứa N số nguyên A_1, A_2, ..., A_N (1 <= A_i <= 10^9), là giá trị của các viên ngọc.

OUTPUT FORMAT

In ra một số nguyên duy nhất là giá trị chênh lệch tuyệt đối nhỏ nhất giữa tổng giá trị của hai nhóm.

Ví dụ:

Input:

3
10 4 6

Output:

0

Giải thích:

• Tổng giá trị của tất cả các viên ngọc là 10 + 4 + 6 = 20.
• Có thể chia thành hai nhóm như sau:
  • Nhóm 1: {10}, Tổng = 10
  • Nhóm 2: {4, 6}, Tổng = 10
• Chênh lệch tuyệt đối: |10 - 10| = 0. Đây là giá trị nhỏ nhất có thể.

Input:

4
3 7 8 10

Output:

2

Giải thích:

• Tổng giá trị của tất cả các viên ngọc là 3 + 7 + 8 + 10 = 28.
• Để chênh lệch nhỏ nhất, ta muốn tổng của một nhóm gần với 28/2 = 14 nhất.
• Nếu nhóm 1 là {3, 7}, tổng = 10. Nhóm 2 là {8, 10}, tổng = 18. Chênh lệch = |10-18|=8.
• Nếu nhóm 1 là {3, 8}, tổng = 11. Nhóm 2 là {7, 10}, tổng = 17. Chênh lệch = |11-17|=6.
• Nếu nhóm 1 là {7, 10}, tổng = 17. Nhóm 2 là {3, 8}, tổng = 11. Chênh lệch = |17-11|=6.
• Nếu nhóm 1 là {8}, tổng = 8. Nhóm 2 là {3, 7, 10}, tổng = 20. Chênh lệch = |8-20|=12.
• ...
• Chia tối ưu:
  • Nhóm 1: {3, 7, 8}, Tổng = 18
  • Nhóm 2: {10}, Tổng = 10
  • Chênh lệch = |18 - 10| = 8.
• Wait, this problem is standard Partition Problem, which has a specific solution. Let me find a better split.
• Better split for {3, 7, 8, 10}, total 28, target sum 14:
  • Nhóm 1: {3, 10}, Tổng = 13. Nhóm 2: {7, 8}, Tổng = 15. Chênh lệch = |13-15|=2.
  • Hoặc: {7}, {3,8,10} => |7-21|=14
  • Hoặc: {8}, {3,7,10} => |8-20|=12
  • Hoặc: {3,7}, {8,10} => |10-18|=8
  • Hoặc: {3,8}, {7,10} => |11-17|=6
  • Hoặc: {7,8}, {3,10} => |15-13|=2.
• Giá trị chênh lệch nhỏ nhất là 2.