Re: [問題] 一個關於計算最佳組合的問題

[weijr (Beware of the Monkey)]

※ 引述《ling123 (@@)》之銘言：
: 首先非常感謝你的回答~
: 板子通常會被區分成100~200個區域
: 一次會有50~70片~
: 我們是想運用在當兩個產品組合時~
: 讓有相同問題的板子盡量放在一起~以減少報廢品
: 我們現在遇到的問題是~要是以嘗試所有組合來算出最佳解當出發點的話
: 這樣花的時間難以估計()~也不符合成本效益~
: 所以想要看看有沒有可能以資料結構或演算法來求最佳解~
這是  Maximum Weight Perfect Matching
你把每個板子看成一個頂點，兩個板子相連一條邊，
這樣成為一個圖。然後每條邊上賦予一個 Weight=相同的標記數量。
你的問題就是要找到一個 Matching 讓標記數量最多。
搜尋一下網路或者找一下書，就可以找到不錯的演算法。

--
  http://weijr-note.blogspot.com  筆記筆記
  http://weijr.b81.org/poker      好膽玩家

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 134.208.26.237
推 ykjiang:推
→ ykjiang:漂亮