30/09/2018, 16:21

Ai rảnh chỉ giáo em bài chia kẹo bằn quy hoạch động với

các đại ca giúp rm giải thuật bài này luôn nhé.

Cho n gói kẹo. Gói kẹo thứ i có a[i] viên kẹo. Yêu cầu bài toán : tìm cách chia n gói thành 2 phần sao cho tổng số kẹo chênh lệch giữa 2 phần là ít nhất. (

... viết 18:29 ngày 30/09/2018

Bài này có thể quy về bài toán: Chia mảng số nguyên a thành 2 phần sao cho S1 - S2 min.

Trên là video hướng dẫn. Mình chỉ biết tìm xem có cách chia mảng thành 2 phần bằng nhau hay không thôi. Chứ tìm giá trị min thì mình không rõ. Ai làm được cho mình xin code tham khảo luôn.

Hồ Thế Chín viết 18:31 ngày 30/09/2018

Gọi T là tổng số kẹo của n gói. Chúng ta cần tìm số S lớn nhất thoả mãn:
S ≤ T/2.
Có một dãy con của dãy a có tổng bằng S. Khi đó sẽ có cách chia với chênh lệch 2 phần là
T - 2S 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.

chu đức anh viết 18:36 ngày 30/09/2018

cảm ơn các anh. em đã code song bằng ngôn ngữ c++ rồi

Bài liên quan
0