组合优化问题举例

Seawind2012

+ G% V, I; t* D7 f- w& \7 GTSP旅行售货员问题
' O7 a. b1 V& n0 r- A
% B: K# l% U) X* p   从某个城市出发，经过n个指定的城市，每个城市只能且必须经过一次，最后回到出发城市，如何安排旅行商的行走路线以使总路程最短？

约束机器排序问题

' p# s/ O! w: f8 i- v     n个加工量为di(i=1,2,… n)的产品在一台机器上加工，机器在第t个时段的工作能力为ct,完成所有产品加工的最少时段数。

0 p: M, k' l" [指派问题

6 G5 @" }" X7 V, l8 ?    一家公司经理准备安排N名员工去完成N项任务，每人一项。由于各员工的特点不同，不同的员工去完成同一项任务时获得的回报是不同的。如何分配工作方案可以获得最大收益？
5 S, Y3 w& M' Z& j. m  m9 I
9 Y2 m- c) o4 S! Z0-1背包问题

* x9 j9 k9 K5 R: j, |4 T* H   设有一个容积为b的背包，n个体积分别为ai(i=1,2,… n),价值分别为ci (i=1,2,… n)的物品，如何以最大的价值装包？

  ^" C& e1 x1 g' g2 e1 R/ a装箱问题
) ]# Y4 S# ^; ^
   如何用个数最少的尺寸为1的箱子装进n个尺寸不超过1的物品？

% j8 w$ e+ ?5 W/ \: S/ H8 z  wSAT问题
2 O- _  f. `, d* ?7 O
     称判定一个公式是否存在一个模型的问题为可满足性问题(以后简称为SAT问题)。如果一个公式存在模型，则称该公式是可满足的，否则称为不可满足的。

皇后问题

% |2 T4 s- e+ e( {7 _6 t- Z& N' S    在n×n的国际象棋棋盘上，摆放n个皇后，使得n个皇后之间不能相互“捕捉”？

arial

重要的基础

wuxiedanran

还是洗洗，回家睡觉吧……

龙龙鲸鱼寜

谢谢诶楼主分享
+ c+ b! |" D+ G8 S: [- Q5 r3 v