作者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