Tin học Bài tập nâng cao

[Deathheart]

[TẶNG BẠN] TRỌN BỘ Bí kíp học tốt 08 môn
Chắc suất Đại học top - Giữ chỗ ngay!!

ĐĂNG BÀI NGAY để cùng trao đổi với các thành viên siêu nhiệt tình & dễ thương trên diễn đàn.

Có N gói kẹo đánh số từ 1 .. N, gói thứ i có số kẹo là Ai, i=1..N. N gói kẹo được chia làm 2 phần khác nhau.
Yêu cầu: tìm cách chia sao cho độ chênh lệch tổng số kẹo giữa hai phần là ít nhất
Dữ liệu vào: file văn bản CANDY.INP:
- Dòng đầu ghi N, N<=200
- Dòng thứ hai ghi lần lượt A1, A2, ..., AN. Ai<=1000
Kết quả: file văn bản CANDY.OUT:
- Dòng đầu ghi D là độ chênh lệch ít nhất
- Dòng thứ 2 ghi số hiệu các gói thuộc phần thứ nhất
- Dòng thứ 3 ghi số hiệu các gói thuộc phần thứ 2
Ví dụ:

CANDY.INP	CANDY.OUT
4 3 4 7 12	2 3 4 7 12

[TBODY] [/TBODY]

 

[Trâm Nguyễn Thị Ngọc]

Có N gói kẹo đánh số từ 1 .. N, gói thứ i có số kẹo là Ai, i=1..N. N gói kẹo được chia làm 2 phần khác nhau.
Yêu cầu: tìm cách chia sao cho độ chênh lệch tổng số kẹo giữa hai phần là ít nhất
Dữ liệu vào: file văn bản CANDY.INP:
- Dòng đầu ghi N, N<=200
- Dòng thứ hai ghi lần lượt A1, A2, ..., AN. Ai<=1000
Kết quả: file văn bản CANDY.OUT:
- Dòng đầu ghi D là độ chênh lệch ít nhất
- Dòng thứ 2 ghi số hiệu các gói thuộc phần thứ nhất
- Dòng thứ 3 ghi số hiệu các gói thuộc phần thứ 2
Ví dụ:

CANDY.INP	CANDY.OUT
4 3 4 7 12	2 3 4 7 12

[TBODY] [/TBODY]

Bài này em chưa check, anh check giúp em với. Em dựa vào cái sườn hướng dẫn "

Gọi T là tổng số kẹo của gói kẹo. Chúng ta cần tìm số S lớn nhất thõa mãn:
S≤T/2.

• Có một dãy con a có tổng bằng S

Khi đó sẽ có cách chia giữa hai phần 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.""
Rồi em viết ra nên ko biết đúng hay sai đb là phần sau của bài đó anh