《遗传算法与组合优化.》由会员分享，可在线阅读，更多相关《遗传算法与组合优化.（4页珍藏版）》请在金锄头文库上搜索。
1、 遗传算法与组合优化. 第四章 遗传算法与组合优化 4.1 背包问题（knapsack problem ） 4.1.1 问题描述 0/1背包问题：给出几个尺寸为S 1，S 2，S n 的物体和容量为C 的背包，此处S 1，S 2，S n 和C 都是正整数；要求找出n 个物件的一个子集使其尽可能多地填满容量为C 的背包。 数学形式： 最大化 =n i i i X S 1 满足 ,1C X S n i i i = n i X i 1,1,0 广义背包问题：输入由C 和两个向量C (S 1，S 2，S n )和P (P 1，P 2，P n )组成。设X 为一整数集合，即X 1，2，3，n ，T 为X
2、 的子集，则问题就是找出满足约束条件T i i C X ，而使T i i P 获得最大的子集T ，即求S i 和P i 的下标子集。 在应用问题中，设S 的元素是n 项经营活动各自所需的资源消耗，C 是所能提供的资源总量，P 的元素是人们从每项经营活动中得到的利润或收益，则背包问题就是在资源有限的条件下，追求总的最大收益的资源有效分配问题。 广义背包问题可以数学形式更精确地描述如下： 最大化 =n i i i X P 1 满足 ,1C X S n i i i = n i X i 1,1,0 背包问题在计算理论中属于NP 完全问题，其计算复杂度为O (2n )，若允许物件可以部分地装入背包，即允
3、许X ，可取从0.00到1.00闭区间上的实数，则背包问题就简化为极简单的P 类问题，此时计算复杂度为O (n )。 第四章 遗传算法与组合优化 4.1 背包问题（knapsack problem ） 4.1.1 问题描述 0/1背包问题：给出几个尺寸为S 1，S 2，S n 的物体和容量为C 的背包，此处S 1，S 2，S n 和C 都是正整数；要求找出n 个物件的一个子集使其尽可能多地填满容量为C 的背包。 数学形式： 最大化 =n i i i X S 1 满足 ,1C X S n i i i = n i X i 1,1,0 广义背包问题：输入由C 和两个向量C (S 1，S 2，S n
4、)和P (P 1，P 2，P n )组成。设X 为一整数集合，即X 1，2，3，n ，T 为X 的子集，则问题就是找出满足约束条件T i i C X ，而使T i i P 获得最大的子集T ，即求S i 和P i 的下标子集。 在应用问题中，设S 的元素是n 项经营活动各自所需的资源消耗，C 是所能提供的资源总量，P 的元素是人们从每项经营活动中得到的利润或收益，则背包问题就是在资源有限的条件下，追求总的最大收益的资源有效分配问题。 广义背包问题可以数学形式更精确地描述如下： 最大化 =n i i i X P 1 满足 ,1C X S n i i i = n i X i 1,1,0 背包问题在计算理论中属于NP 完全问题，其计算复杂度为O (2n )，若允许物件可以部分地装入背包，即允许X ，可取从0.00到1.00闭区间上的实数，则背包问题就简化为极简单的P 类问题，此时计算复杂度为O (n )。
