贪心法适用范围 ■满足优化原则的组合优化问题 若满足贪心选择性质得最优解,否则得近似解 什么是组合优化问题 Ⅹ有穷的变量集合一活动集合S <sifi>|1<==n} Y有穷的值集合—相容活动集A的规模{1,…n} f(×)目标函数—max|A G约束条件集合一s>=f或5>=f(1<=<j<=n) 个组合优化问题的解是对变量集Ⅹ的一组赋值g:X >Y,并且在满足G中约束条件的前提下使得目标函 数f(×)取得最大(小)值贪心法适用范围 „ 满足优化原则 的组合优化问题 „ 若满足贪心选择性质 得最优解，否则得近似解 „ 什么是组合优化问题 „ X 有穷的变量集合 —活动集合S = {<si,fi>|1<=i<=n} „ Y 有穷的值集合 —相容活动集 A的规模{1, …,n} „ f(x) 目标函数 —max |A| „ G 约束条件集合 —si>=fj 或sj>=fi (1<=i<j<=n) „ 一个组合优化问题的解是对变量集 X的一组赋值g:X- >Y，并且在满足 G中约束条件的前提下使得目标函 数f(x)取得最大（小）值