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. (
Bài liên quan
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.
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.
cảm ơn các anh. em đã code song bằng ngôn ngữ c++ rồi