01/10/2018, 14:12
Xin ý tưởng bài tập về ma trận
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
Bài liên quan
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].
Mình vẫn chưa hiểu cách duyêt lắm. Bạn nói rõ hơn đc không?
Hungarian algorithm
The Hungarian method is a combinatorial optimization algorithm that solves the assignment problem in polynomial time and which anticipated later primal-dual methods. It was developed and published in 1955 by Harold Kuhn, who gave the name "Hungarian method" because the algorithm was largely based on the earlier works of two Hungarian mathematicians: Dénes Kőnig and Jenő Egerváry. James Munkres reviewed the algorithm in 1957 and observed that it is (strongly) polynomial. Since then the algorithm...
coi trên topcoder ko hiểu gì hết @_@
topcoder.com
Community - Data Science - Data Science Tutorials - Assignment Problem and...
Community - Data Science - Data Science Tutorials - Assignment Problem and Hungarian Algorithm
Những số 0 trong ma trận rất quan trọng.
Nếu số số 0 < số dòng thì:
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.
yes. mình hiểu rồi. cảm ơn b nhiều nha