Re: [問題] 給一個m*n(m<=n)矩陣，每列取一個非零ꐠ…
※ 引述《tkcn (小安)》之銘言：
: 如果問題是要找出一組 one-to-one 對應，
: 可以把問題轉成 Maximum Bipartite Matching，
: 然後用 Hangerian Algorithms(匈牙利演算法) 去找出一組解。
: 這類問題如果只需要計算所有解的 "數量" 且數字不大時， (n<20)
: "也許" 還有機會用 DP 算出。複雜度大概 O( 2^n * ... )
: 至於要算到 20*33，我個人是認為沒有辦法。
提供一下DP解法。
Bipartite Matching 就是有兩堆東西，然後連連看：
http://163.27.162.1/98music/%E9%80%A3%E9%80%A3%E7%9C%8B.jpg
想要連連看，第一直覺，
當然就是第一個連第一個、第二個連第二個、....這樣囉。
接下來才會繼續考慮其他的連法。
事實上我們可以把下面的東西重新排列一下，
就可以一直保持一連一、二連二了。
所以方法就是：
窮舉下面東西的全部排列方式，
每一種排列方式都很容易就能計算出連連看的結果了。
用DP的話，可以 O(n^2 * 2^n) 解出來。
大致上就跟 Travelling Salesman Problem 的 DP 解法長得差不多。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 59.115.154.35
※ 編輯: DJWS 來自: 59.115.154.35 (05/24 17:06)
→
05/24 21:02, , 1F
05/24 21:02, 1F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 3 之 4 篇)：