作者ling123 (@@)
看板Programming
標題Re: [問題] 一個關於計算最佳組合的問題
時間Thu Apr 19 08:19:14 2007
首先非常感謝你的回答~
板子通常會被區分成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
1F：推 ykjiang:幾千種組合而已，可以一個一個試... 203.73.175.9 04/19 13:28
2F：推 ykjiang:如板子大且不要求絕對精度，可用抽樣法 203.73.175.9 04/19 13:33
3F：推 ling123:以60片而言應該不會只有幾千種組合.. 203.66.215.100 04/20 08:21
4F：→ ling123:光是要先抽哪兩片當第一組就有幾千種可能 203.66.215.100 04/20 08:23
5F：→ ling123:然後要再抽第二組時將會變成幾十萬或百萬. 203.66.215.100 04/20 08:24
6F：→ ling123:當60片要湊成30組時 應該不會只有幾千種~ 203.66.215.100 04/20 08:26
7F：→ ykjiang:一時不察 :p 211.74.124.55 04/21 01:08
8F：→ ykjiang:看來你得去拉斯維佳或蒙地卡羅逛逛了 :) 211.74.124.55 04/21 01:10
9F：推 ykjiang:的確可以用 DP 法解決。 211.74.124.55 04/21 01:27