Hỏi cách suy nghĩ và giải bài tập bằng phương pháp quy hoạch động

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 :smiley:
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
1 Like

Việc xét hiệu trên và dưới của domino tương dương việc đặt dấu (+,-) cho hiệu trên dưới của 1 domino. Nó tương dương với việc xếp thành hai nhóm (dấu +) và (dấu -) sao cho hiệu trị tuyệt đối nhỏ nhất.
Việc xét tìm giá trị đó thì chỉ việc sinh ra tất cả giá trị của nó bằng cách duyệt mảng
F[1…n][-n6…n6] như sau

for i =0->n:
For j=-6n ->6n:
    if F[i-1][j]:
       F[i][j+a[i]-b[i]]=True
       F[i][j-a[i]+b[i]]=True

việc duyệt mảng f sao cho có trị tuyệt đối nhỏ nhất là kết quả
Việc truy vết thì bạn tự nghĩ :smiley:

4 Likes

Qui hoạch động lấy tư tưởng chia để trị :smiley: với 1 bài toán thường thì mình sẽ đi từ kết quả để tìm ra cách chia nhỏ bài toán :smiley: ví dụ bài trên giả sử đã xếp đc cấu hình tối ưu từ 1 -> n-1 thì cấu hình thứ n cần xếp ntn :v:
TH1: ko lật ô thứ n
Th2: lật ô thứ n
Xét 2 TH này là bao quát tất cả các trường hợp xẩy ra.
Từ đó để biết được xem đến con thứ n thì nên lật hay không thì điều cần là các con phía trước đã xếp đc tổng là bao nhiêu => Khởi đầu: F[i,s] là giá trị để nhận biết xem dùng đến con thứ i có tạo ra tổng s hay ko.F[i,s]= F[i-1,s-(a[i] ± b[i])] từ đây đủ để tìm ra yêu cầu là tổng bé nhất rồi :))
Đọc lại bài toán thấy còn yêu cầu ít nhất, nhận thấy cái hàm F[i,s] còn dư dả quá :v ép cho nó thành tạo thành tổng s đến con thứ i lật ít nhất thì sao :v

2 Likes

Em cám ơn :smiley:
Vậy với những trường hợp phân thành (+),(-) như bài này có thể dùng phương pháp này phải không

Em đang học cách suy nghĩ, chỉ cần hướng thôi ạ. Kiểu nhìn nhận thấy điều A thì ta suy được mình phải làm gì với kiểu như thế. Bài kia em xong rồi :sweat_smile: cám ơn anh AI_Android và Gió.
Trang không cho chèn ảnh, trình bày khó quá :persevere:

Cho một bảng số A gồm M dòng, N cột, các giá trị của bảng A chỉ là 0 hoặc 1. Ta muốn cắt bảng A thành các hình chữ nhật con sao cho các hình chữ nhật con có giá trị toàn bằng 1 hay toàn bằng 0. Một lần cắt là một nhát cắt thẳng theo dòng hoặc theo cột của một hình chữ nhật thành hai hình chữ nhật riêng biệt. Cứ tiếp tục cắt cho ñến khi hình chữ nhật toàn bằng 1 hay toàn bằng 0. Hãy tìm cách cắt ñể ñược ít hình chữ nhật nhất mà các hình chữ nhật con có giá trị toàn bằng 1 hay toàn bằng 0.

Ví dụ: Bảng số 5×5 sau ñược chia thành 8 hình chữ nhật con.
0 1 0 0 1
0 1 0 0 1
1 1 0 0 1
1 1 1 0 0
0 0 1 0 0

0  | 1 | 0   0 | 1

0  | 1 | 0   0 | 1
--------
1    1 | 0   0 | 1
       -----------
1    1 | 1 | 0   0
--------
0   0  | 1 | 0   0

Dữ liệu vào trong file HCN2.INP

  • Dòng ñầu là 2 số nguyên dương M, N (M,N≤30)
  • M dòng tiếp theo, mỗi dòng N số chỉ gồm 0 hoặc 1 thể hiện bảng số A

Kết quả ra file HCN2
Gồm 1 dòng duy nhất chứa một số duy nhất là số hình chữ nhật ít nhất

1 Like

Rê ảnh thả vào phần Reply, ảnh sẽ tự động được tải lên (nhớ đợi cho ảnh upload xong nhé), áp dụng cho cả việc tạo topic mới luôn :grin:

1 Like

Cái này giờ mới biết, chẳng thấy topic nào có ảnh tưởng không có chức năng. Hóa ra dùng HTML :joy:

Ai giúp với, nhân tiện cho mail hay địa chỉ gì để liên lạc nhờ chỉ giáo dùm

F[a,b,c,d] là hình số hình chữ nhật ít nhất trong hình nhật có đỉnh trái trên là a,b chiều dài,rộng là c,d
init:

1: if S[a,b,c,d] =c*d hoac bang 0 //cac phan tu trong hinh chu nhat dang xet la giong nhau
    thi F[a,b,c,d]=1; else F[a,b,c,d]=c*d;
F[a,b,c,d]= min ( F[a,b,c,k]+F[a,b+k,c,d-k], F[a,b,t,d]+ F[a+t,b,c-t,d] )

O(n^2*m^2*(n+m))

3 Likes

Phương pháp tham lam hình như không dùng được với bài này.

83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?