Bai toan xoay thanh DOMINO

[QUOCDN]

Tôi có bài toán như sau :

Cho than h DOMINO xếp theo chiều dọc như sau :
1 1 3 2 6
2 6 5 6 4

Mỗi thanh DOMINO gồm 2 phần : phần trên và phần dưới . Trên mỗi phần có mốt số từ 1 đến 6 . yêu cầu đặy ra là hãy tìm cách xoay các thanh ( 180 độ)sao cho để sau khi xoay chênh lệch giữa tổng trên và tổng dưới là ít nhất.

Giới hạn : N< = 1000

Các bạn thử tìm thuật giải xem ?

[khôngtên]

Bác áp dụng thuật toán chia kẹo thế là OK thôi !

[KEM_WALL]

bạn cho hỏi thuật giải chia kẹo là thế nào ?

[lugia]

Bài toán chia kẹo: cho N túi kẹo, số kẹo trong túi thứ i là A[i]. Bạn hãy chia các túi kẹo ra làm hai phần sau cho số kẹo chênh nhau giữa hai phần là ít nhất. :)
Bài này ta có thể dùng qui hoạch động:
- Dùng 1 mảng boolean thật lớn để đánh dấu các số kẹo có thể ghép được: mảng B.vd: B[12]=true-> ta có thể ghép các túi kẹo thành 1 phần có 12 cái kẹo.
- Tạo cơ sở qui hoạch động: B[A[1]]=true, B[A[2]]=true -> B[A[n]]=true, và B[0]=true.
- Dùng 1 vòng For i từ 1->n để duyệt qua hết các gói kẹo, ở mỗi bước của vòng For ta tìm trong mảng B phần tử nào bằng true vd B[k]=true suy ra B[k+A[i]]=true, ta tạo thêm 1 mảng C để đánh dấu bước đi: C[k+A[i]]=k.

max:= phần tử lớn nhất của A.
For i:=1 to n do
begin
p:=max;
For k:=1 to max do {max là phần tử lớn nhất của mảng B mà bằng true}
if (B[k]=true) and (k-C[k]<>A[i]) then
begin
B[k+A[i]]:=true; C[k+A[i]]:=k;
if k+A[i]>p then p:=k+A[i];
end;
max:=p;
end;

- Làm như trên ta sẽ tìm được các cách ghép: vd: nếu B[i]=true thì có thể ghép các túi kẹo thành 1 phần có i cái kẹo. Vì vậy, ta đặt biến t là tổng số kẹo thì phần tử B[m] gần t/2 nhất là cách ghép tối ưu nhất, sau để ta sẽ lần theo mảng C để ghi ra các bước chọn của cách chọn B[m].

Đấy là các bước làm khái quát của thuật toán, bạn hãy áp dụng bài này để làm bài DOMINO, có gì chưa hiểu cứ hỏi mình. Chúc bạn thành công:)