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

[ling123 (@@)]

首先非常感謝你的回答~
板子通常會被區分成100~200個區域
一次會有50~70片~
我們是想運用在當兩個產品組合時~
讓有相同問題的板子盡量放在一起~以減少報廢品

我們現在遇到的問題是~要是以嘗試所有組合來算出最佳解當出發點的話
這樣花的時間難以估計()~也不符合成本效益~
所以想要看看有沒有可能以資料結構或演算法來求最佳解~


※ 引述《ykjiang (York)》之銘言：
: 板子多大？
: 最多有幾塊？
: 很好奇這個問題的實際應用？
: 無論如何，給你一點提示：
: 轉成一維後，可以很方便用 or 運算當作「疊」這個動作，
: 然後數裡面有幾個 1 就知道聯集後的標示區大小
: ※ 引述《ling123 (@@)》之銘言：
: : 問題是這樣的
: : 我有幾張板子~板子上有區分出一些區域(每塊板子的區域都一樣)
: : 每塊板子上的區域會有一些標示(數量不一)
: : 我想要算出當兩兩成對疊在一起的時候~
: : 怎麼疊他的標示區域會最小(就是將標示區做聯集)
: : 如
: : #表示空白區域 O表示有標示區域
: : 板子一     板子二    兩張疊在一起
: : # # O      # O #     # O O
: : # # #      O # #     O # #
: : # # #      # # O     # # O
: : 當有10片時~就是湊成五對~要怎麼湊才能讓數值最小
: : 用程式跑的話用我知道用迴圈...
: : 可是當我的板子有百片或是板子區域細切到百區的時候~
: : 用程式比對就要比對很久..(太多種組合了)
: : 想問說在資料結構中有沒有快速的計算方式,可以計算出結果
: : 不管有沒有答案還是謝謝大家看完這個問題~謝謝~

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 203.66.215.100
推 ykjiang:幾千種組合而已，可以一個一個試...
推 ykjiang:如板子大且不要求絕對精度，可用抽樣法
推 ling123:以60片而言應該不會只有幾千種組合..
→ ling123:光是要先抽哪兩片當第一組就有幾千種可能
→ ling123:然後要再抽第二組時將會變成幾十萬或百萬.
→ ling123:當60片要湊成30組時 應該不會只有幾千種~
→ ykjiang:一時不察 :p
→ ykjiang:看來你得去拉斯維佳或蒙地卡羅逛逛了 :)
推 ykjiang:的確可以用 DP 法解決。