作者weijr (Beware of the Monkey)
看板Programming
标题Re: [问题] 一个关於计算最佳组合的问题
时间Fri Apr 20 13:14:04 2007
※ 引述《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
1F：推 ykjiang:推 211.74.124.55 04/21 02:19
2F：→ ykjiang:漂亮 211.74.124.55 04/21 02:22