精选优质文档-倾情为你奉上第四章 遗传算法与组合优化4.1 背包问题（knapsack problem）4.1.1 问题描述0/1背包问题：给出几个尺寸为S1，S2，Sn的物体和容量为C的背包，此处S1，S2，Sn和C都是正整数；要求找出n个物件的一个子集使其尽可能多地填满容量为C的背包。数学形式：最大化满足广义背包问题：输入由C和两个向量C(S1，S2，Sn)和P(P1，P2，Pn)组成。设X为一整数集合，即X1，2，3，n，T为X的子集，则问题就是找出满足约束条件，而使获得最大的子集T，即求Si和Pi的下标子集。在应用问题中，设S的元素是n项经营活动各自所需的资源消耗，C是所能提供的资源总量，P的元素是人们从每项经营活动中得到的利润或收益，则背包问题就是在资源有限的条件下，追求总的最大收益的资源有效分配问题。广义背包问题可以数学形式更精确地描述如下：最大化满足背包问题在计算理论中属于NP完全问题，其计算复杂度为O(2n)，若允许物件可以部分地装入背包，即允许X
