资源预览内容
第1页 / 共4页
第2页 / 共4页
第3页 / 共4页
亲,该文档总共4页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
遗传算法与组合优化. 第四章 遗传算法与组合优化 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 的子集,则问题就是找出满足约束条件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 )。 第四章 遗传算法与组合优化 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 的子集,则问题就是找出满足约束条件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 )。
收藏 下载该资源
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号