Mọi người có thể chỉ cho em cách mọi người suy nghĩ để lập trình một bài tập quy hoạch động được không
Em đang học Pascal phần quy hoạch động. Mong mọi người chỉ bảo.
Nhân tiện dạy em hướng suy nghĩ bài này với
Cho n quân đô-mi-nô xếp dựng đứng theo hàng ngang và được đánh số từ 1 đến n. Quân đô-mi-nô thứ i có số ghi ở ô trên là a[i] và số ghi ở ô dưới là b[i]. Xem hình vẽ:
|1| |1| |4| |4| |0| |6| |6| |3| |1| |1| |6| |1|
Biết rằng 1 ≤ n ≤ 100 và 0 ≤ a[i], b[i] ≤ 6 với ∀i: 1 ≤ i ≤ n. Cho phép lật ngược các quân đô-mi-nô. Khi một quân đô-mi-nô thứ i bị lật, nó sẽ có số ghi ở ô trên là b[i] và số ghi ở ô dưới là a[i].
Vấn đề đặt ra là hãy tìm cách lật các quân đô-mi-nô sao cho chênh lệch giữa tổng các số ghi ở hàng trên và tổng các số ghi ở hàng dướii là tối thiểu. Nếu có nhiều phương án lật tốt như nhau, thì chỉ ra phương án phải lật ít quân nhất.
Như ví dụ trên thì sẽ lật hai quân Đô-mi-nô thứ 5 và thứ 6. Khi đó:
- Tổng các số ở hàng trên = 1 + 1 + 4 + 4 + 6 + 1 = 17
- Tổng các số ở hàng dưới = 6 + 3 + 1 + 1 + 0 + 6 = 17