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. (
Giải bài toán chia kẹo bằng quy hoạch động
2 Likes
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.
2 Likes
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.
5 Likes
cảm ơn các anh. em đã code song bằng ngôn ngữ c++ rồi
3 Likes
Cảm ơn bạn!
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?