Xin ý tưởng bài tập về ma trận

Lam_Ngoc · January 18, 2018, 10:33am

Cho ma trận vuông C = (cij) cấp N (1<= i, j <= N<=100) gồm N^2 số tự nhiên (các số không nhất
thiết phải khác nhau) ghi lại trong file matran.in theo khuôn dạng sau :

Dòng đầu tiên ghi lại số tự nhiên N là cấp của ma trận vuông C;
N dòng kế tiếp ghi lại ma trận vuông C = (cij). Hai phần tử khác nhau của ma trận
được ghi cách nhau bởi một vài khoảng trống.
Hãy sử dụng thuật toán quay lui viết chương trình lấy trên mỗi hàng, mỗi cột duy nhất
một phần tử của ma trận C sao cho tổng các phần tử này là nhỏ nhất. Kết quả tìm được
ghi lại trong file ketqua.out theo khuôn dạng:
Dòng đầu tiên ghi lại tổng giá trị nhỏ nhất của N phần tử tìm được;
N dòng kế tiếp, mỗi dòng ghi lại ba số i, j, cij tương ứng với chỉ số hàng, chỉ số cột
và giá trị phần tử tương ứng của ma trận. Ba số được viết cách nhau một vài khoảng
trống.
Ví dụ về file matran.in và ketqua.out:
matran.in
6
10 64 57 29 18 15
34 20 19 30 16 12
57 49 40 16 11 19
29 21 46 26 21 18
28 16 11 21 21 37
15 12 15 48 37 30
ketqua.out
82
1 1 10
2 6 12
3 4 16
4 5 21
5 3 11
6 2 12

rogp10 · January 18, 2018, 11:32am

Bài này duyệt trâu là 100! nếu là min thì chặt nhánh thôi (max mới phải gần đúng).

Một ý tưởng ta sẽ dùng cả min_col_idx[] và min_row_idx[] để “tham”, tức là gom hết những phần tử khác nhau để làm prefix.

MRI = [1, 6, 5, 6, 3, 2]
MCI = [1, 6, 5, 5, 3, 2]

ta thấy rằng MCI[MRI[2]] = 2 nên ta giữ [1, 6, 5, X, 3, 2].

Lam_Ngoc · January 18, 2018, 7:18pm

Mình vẫn chưa hiểu cách duyêt lắm. Bạn nói rõ hơn đc không?

tntxtnt · January 19, 2018, 12:42am

coi trên topcoder ko hiểu gì hết @_@

rogp10 · January 19, 2018, 3:46pm

Lấy mỗi số trên dòng trừ đi min của dòng đó.
Rồi lấy mỗi số trên cột trừ đi min của cột đó.

Những số 0 trong ma trận rất quan trọng.

Chọn 0 theo dòng: Nếu dòng có đúng 1 số 0 thì đánh dấu nó và gạch bỏ dòng đó.
Chọn 0 theo cột: tương tự.

Nếu số số 0 < số dòng thì:

Cộng trả lại min của phần chưa gạch vào các giao điểm đường gạch.
Trừ những phần tử chưa gạch với min.
Làm lại từ đầu.
Ngược lại, kết quả là vị trí của tất cả số 0 được chọn.

Đây là một ma trận khác:
08 10 12 16
11 11 15 08
09 06 05 14
15 14 09 07
1: [0 2 4 8 | 3 3 7 0 | 4 1 0 9 | 8 7 2 0]
2T: [0 3 4 8 | 1 2 0 6 | 4 7 0 2 | 8 0 9 0]
2: [0 1 4 8 | 3 2 7 0 | 4 0 0 9 | 8 6 2 0]
bỏ: cột 1, cột 4.
Bỏ qua 1, 4: gạch dòng 3. Chỉ mới có 3 số 0 thôi.
Dòng 3 trở thánh: [5 0 0 10].
Ma trận: [0 0 3 8 | 3 1 6 0 | 4 0 0 9 | 8 5 1 0]

Do 0 là min rồi nên ta bỏ: cột 4; dòng 1, dòng 3. Mới có 3 số 0 thôi.

Lam_Ngoc · January 19, 2018, 3:45pm

yes. mình hiểu rồi. cảm ơn b nhiều nha