背包设计范文

背包设计范文（精选11篇）

背包设计 第1篇

本节以较为常见的日常运动背包为例, 深入浅出的介绍这一类包体的结构设计、部件组成以及样板制作的方法和步骤。

1 背包的结构及部件设计

此款背包结构相对较为简单, 主要由前幅、后幅、前幅斜插袋、侧围、网袋以及内里的电脑夹层袋和手机袋构成。前幅作为包体最主要、最明显的部件其结构设计、部件分割显得尤为重要。

1.1 前幅的设计

前幅为包体中相对面积较大的部件, 其部件分割、装饰设计是体现包体风格特征的主要部件。本款包前幅两侧斜插袋的设计, 底部多层次的部件分割, 动感十足的面料图案将包体的运动气息体现的淋漓尽致。整个前幅部件由前幅中贴、侧贴、下贴片和底片等5个部件组成 (图1-5) 。

斜插袋是在前幅上片的基础上进行分割设计的, 大致从上片高度的1/3处斜向分割, 其底部占上贴片长度的1/3左右。两条分割线将前幅上片划分为三个部分, 在分割线的位置设计拉链, 使其成为有实用功能的斜插袋。

前幅下端部分被横向分割为两层, 采用车反内包边的形式, 外观不漏线迹。同时上层的部件又被分为三个小部件, 中间部件上贴缝有挂钩带, 便于在登山时挂置一些小物件。

1.2 后幅及侧围的设计

后幅设计相对来说简单一些, 后幅为一平面部件, 通常托有珍珠棉来提高其舒适度 (图1-6) 。此款包的后幅上同时还设计有三块单独的海绵托料, 其上部采用透气性较好的网布作为表层, 使其不仅柔软舒适, 而且透气性得到提高。

包体侧围由侧围下片、拉链前围和拉链后围三部分组成 (图1-7) , 其中拉链位置设计为斜向形式, 故而, 拉链前围为上部窄、下部宽的结构, 而拉链后围则正好相反, 成为上部宽、下部窄的形状。拉链处设计有宽约2 cm的拉链护片, 不仅外观时尚大方, 而且能很好地保护拉链。侧围分割线为由后向前的斜向分割, 在分割线向上约1 cm的位置设计有侧网袋, 网袋的形状与侧围下片完全一致, 只是袋口尺寸略大一些, 并采用松紧布收口, 这样不仅能增大网袋内部的空间, 还能保障内置物品的安全性。

2 背包尺寸规格的确定

包体各部件尺寸的确定主要依据包体的风格特征、部件之间的比例关系以及包体的功能设计等因素。此款包的尺寸规格主要包括基础尺寸、前幅各部件、侧围各部件以及内里零部件的尺寸规格。

2.1 包体基础尺寸的确定

根据包体的使用功能其尺寸规格应属于体积较大型的背包, 大体尺寸如下 (图2-1) :包体高度约为50 cm, 底部长度为30 cm, 上端长度为24 cm左右, 其宽度为20cm。侧围下端宽20 cm, 上端约为16 cm。

2.2 前幅各部件尺寸的确定

包体前幅从横向被分割为上贴片、中贴片及下贴片三大部分。其高度约为36 cm。其中上贴片背斜向拉链袋分割为左、中、右片三个部件, 其分割线为拉链位置, 拉链上端距前幅顶部约10 cm, 下端在中贴片上边缘的1/3处。

中贴片为一中间宽、两端窄的环形结构, 其中中间高度为8 cm, 两端高度为5 cm左右。同时被竖向的分割线划分为三个部分, 其分割线均为沿拉链下端做总贴片下边缘的垂线而得到, 基本上也属于长度三等份的位置。

下贴片的上端为中贴片的下边缘, 下端长度为包体底部长度30 cm, 高度约为26cm左右。

3.3侧围各部件尺寸的确定

侧围是由侧围下片、拉链前围和拉链后围三个部件组成。其中侧围下片下端为圆弧状, 下端宽度约为20 cm, 上端宽度为16 cm, 高度约为20cm左右。拉链前围顶部宽度为4.5 cm, 底部宽度为10cm, 拉链后围宽度与其正好相反。拉链围的长度为前幅拉链位沿上边缘的周长, 约为72cm左右。侧围的下端设计有网兜, 其高度为21 cm, 上下宽度一致均为20 cm。

2.4 其他零部件尺寸规格的确定

背带是由背带和下端的织带组成, 一般背带的长度约为43 cm左右, 宽度为7 cm左右, 其下端略窄一些呈圆弧形。织带一般选择宽为2.5cm, 长度40 cm左右, 通过其可以进行背带长度的调节。

此款包设计有两个挂钩带, 一个在包体的顶端, 一个在前幅下贴片的中间部件上。一般采用宽为2.5 cm的织带, 长度约为14 cm左右。

3 背包各部件样板的制作

此款背包属于运动型背包, 所以其部件组成较为复杂一些, 要制作完成的样板主要有前后幅、侧围、拉链前围、拉链后围、前幅斜插袋以及前幅下片等各部件的样板。

3.1 前幅正格样板的制作

前幅正格相当于包体前幅的模板, 主要用来反映前幅的部件组成、比例关系等。前幅从横向可以划分为上贴片、中贴片和下贴片三部分, 其中上贴片是由中片及左右片组成, 中贴片沿纵向平均分为三个部分, 下贴片为一整体部件。

其正格的样板制作过程如下 (图3-1) :

(1) 首先, 做一条相互垂直的线段作为样板的中心线, 其交点为O点。

(2) 根据包体的基础尺寸, 以O点为中心向左右各截取OL1=OL2=15 cm, 在以O点为中心向上截取OO1=20cm、OH=70 cm。过H点做OH的垂线并截取HL3=HL4=12 cm, 连接L1L3、L2L4得到一个梯形为前幅正格的基础形状。

(3) 将上端修为大圆弧, 同时将梯形两侧距底部约30cm处向内缩进约2 cm, 其余部分圆滑过渡至L1L2点, 即可得到前幅正格的外轮廓。

(4) 沿中线从O点向上截取OH1=34 cm、OH2=26 cm, 过H1做中线的垂线交于前幅正格的侧边缘为C、D两点, C、D点分别向下5 cm定为E、F两点, 弧形连接E点、H2点和F点。CD线即为前幅正格的上贴片的分割线, EF线为中贴片的分割线。

(5) 在前幅正格的上端距H点约10 cm处定A、B两点, 同时将CD线进行三等份得到C1、D1两点, 连接AC1、BD1即为斜插袋的拉链位置。

(6) 同理将EF线三等分得到E1、F1两点, 连接C1E1、D1F1得到前幅中贴片的分割线。L1EFL2所围成的图形即为前幅的下贴片。

(7) 在A点、B点、C点、E点、F点均做出牙口标记, 同时沿两侧边缘距L1L2向上40cm的位置做出拉链位标记。

3.2 前斜插袋各部件样板的制作

斜插袋是由前幅中片及左右片构成, 其样板均在前幅正格的基础上制作完成。

(1) 前幅中片的样板制作 (图3-2)

在前幅正格样板上将前幅中片复制下来, 上边缘加放0.8 cm的车反量, 下边缘加放0.8 cm的压茬量, 两侧加放0.6 cm的折边量, 同时做出中点牙口标记。

(2) 前幅左右片样板制作 (图3-3)

同理将左右片的形状也复制下来, 与拉链缝合的边缘加放0.6 cm的折边量, 外侧边缘加放0.8 cm的车反量, 下边缘加放0.8 cm的压茬量, 做出拉链位牙口标记。

3.3 前幅中贴片及下贴片各部件的样板制作

(1) 前幅中贴片样板制作 (图3-4)

前幅中贴片由三个部分组成, 将其分别从前幅正格上复制下来, 只有部件分割线处加放0.3 cm的合缝量, 其余部分都加放0.8 cm的车反量即可。

(2) 前幅下贴片样板制作 (图3-5)

将其从前幅正格上复制下来, 四周边缘均加放0.8 cm的车反量, 同时做出中点牙口标记。

3.4 后幅正格及后幅各部件样板的制作

(1) 后幅正格样板制作 (图3-6)

按照包体的基础尺寸, 做一个上底长为26 cm, 下底长为30 cm, 高度为50 cm的梯形, 沿中线将后幅上端向上延伸2 cm至H1点, 并将上端及下端两角分别修为大圆弧即为后幅的基本形状。

在后幅上设计出如图形状的托料, 并做出背带及拉链位的牙口标记。

(2) 后幅样板的制作 (图3-7)

在后幅正格上将后幅形状复制下来, 周边加放0.8 cm的车反量, 并做出背带及拉链位的牙口标记。

(3) 后幅托料及网布样板的制作 (图3-8)

同理将其先逐个复制下来, 周边加放0.6 cm的折边量即为网布样板。同时在网布净样板的基础上周边缩进1cm即为中间海绵的样板。

3.5 侧围正格样板的制作

侧围正格则是根据前幅和后幅样板的基础上来加放弧位 (弯曲程度) 。首先, 侧围的前边缘长度与前幅的侧边缘一致, 后边缘与后幅的侧边缘长度一致。基于以上两点用布带尺或卷尺不断的将前轮廓线进行弯曲试验, 使其后轮廓线长度与后幅一致, 这样即可确定侧围下端的弧度, 进而确定侧围的基本形状 (图3-9) 。侧围正格样板的制作步骤如下 (图3-10) :

(1) 在下边缘向上约20cm处设计侧围的分割线, 前端与前幅样板的高度一致, 后端略高于前端约1.5 cm, 分割线的下面即为侧围下片。

(2) 同时, 在上端距前边缘线2 cm, 下端距后边缘线约2 cm处设计斜向的拉链分割位置, 其中, 分割线的前部分为拉链前围, 后部分为拉链后围。

3.6 侧围下片及侧面网布袋样板的制作

(1) 侧围下片样板的制作 (图3-11)

首先, 将其在侧围正格上复制下来, 上边缘加放0.6 cm的折边量, 前边缘和后边缘均加放0.8 cm的车反量, 并做出与前幅缝合的标记。

(2) 侧面网布袋样板的制作

网布袋比侧围下片高出约1 cm, 上端与下端宽度一致均取18 cm, 除上边缘外周边均加放0.8 cm的车反量。

3.7 拉链前围及后围样板的制作

预防“背包病”:每天清理一次背包 第2篇

有媒体街头随机称量了100人的背包，65%的人背包重量都在3公斤以上，其中最重8.8公斤，相当于15大瓶矿泉水。由于背包太重导致出现“肩膀或后背酸痛”“左右肩膀高低不平”等症状的人，已经占到70%以上。很多人没有意识到，沉重的背包已悄悄成为自己随身携带的一个危险的“健康杀手”。

由于背包太重对健康造成损伤，早已不是什么新鲜事，全球似乎都在面临着“背包病”的威胁。美国有调查显示，每年大约有6000名儿童因书包过重而造成后背损伤。英国《每日邮报》则报道称，一项来自英国脊椎治疗协会的调查发现，英国男性背包的平均重量是6公斤；女性背包的平均重量为2.5公斤，一半以上的英国女性都在忍受背包带来的疼痛。

“背包病”这颗“健康炸弹”一旦爆炸，会给人的全身健康都带来一定的影响。

脖子酸、肩膀疼

台北医科大学附属医院复健科主治医师康峻宏发现，长时间坐在电脑前又背大包的人，往往是肩颈酸痛、肩手麻木无力症状最突出的人群。背包过重会让脖子不自觉地倾向一边，一边肌肉拉伸，一边紧缩，这样很容易导致疼痛。其次，过重的背包还会让肩背部肌肉，如斜方肌和提肩胛肌长期受到压迫，可能出现慢性拉伤。

脊柱弯

驼背、脊柱侧弯、腰椎间盘突出、脊柱关节炎、坐骨神经疼痛等，都可能是背包过重惹的祸。美国波士顿东北大学理疗系主任安·威尔马思指出，你在左肩背了一个5公斤左右的大包，那脊柱右侧的肌肉就要产生15～20公斤的力量，才能维持身体平衡，这种肌肉组织发力的不平衡会牵拉脊柱造成弯曲，造成劳损、发炎。此外，太重的包会导致椎间盘变性、下垂，压迫神经；还会带来坐骨神经痛。

手臂麻

很多女性喜欢将又大又沉的包挎在手臂上，老人买菜时也喜欢将装得满满的帆布袋用手拎着或挽着，时间长了，手臂或手腕很容易酸痛发麻。手腕长时间处于同一姿势或过度使用腕力，会因反复慢性的疲劳损伤导致腕管综合征。

臀部大腿劳损

很多人背着几十斤重的包长时间行走，负重大是膝关节磨损的一个高危因素。背包越重，膝关节的压力越大，容易产生关节问题，最终导致关节炎症。

背包重量每减轻一点，对健康都是巨大的福音——

背包最重不超过4.6公斤

海迪·普拉瑟教授指出，背包最重也不应超过4.6公斤，而且这个重量只是可以偶尔为之。一个快速测量的方法是：找一个重量接近4.6公斤的东西（比如一袋重5公斤的大米），一手拎包，一手拎大米，包的重量别超过大米就行。

女性尽量少带化妆品

美国著名化妆师鲍比·布朗认为，应提倡女性适度化妆；随身携带的化妆包里，最好只带一些简单补妆用的必备化妆品，如粉底、口红或唇彩。当你在包里到处乱翻才能找到化妆品时，证明你带得太多了。

每天清理一次背包

美国专业生活咨询协会会员多娜·斯麦琳建议，每天睡前都应花1分钟检查、清理背包，取出一些不需要的东西，如发票、一些笔、零钱或没喝完的矿泉水，因为这些都会让你的包不知不觉变得越来越沉。

双肩包、斜挎包较安全

安·威尔马思医生指出，双肩包能使身体两侧肩胛骨向后、向下牵拉，从而在负重行走时保持脊柱的平衡和放松。斜挎包将包的重量平均分配到人体一侧肩膀和另一侧腰部之间，从而有效减少脊柱向身体某一侧的弯曲。此外，如果你的东西很多，最好选择尼龙、棉布和帆布材质的包，而不要选本身重量就很大的皮质包。

养成习惯将物品分开放

理疗专家、美国理疗协会发言人帕特里斯·温特医生指出，双手各提3斤重的包，比单手提6斤重的包，更能有效缓解对背部和脖子造成的压力。所以当东西太多时，最好分放到两个包里。

每10分钟换一次肩膀背包

美国按摩协会发言人辛西娅·沃恩医生建议，不管肩背还是手拎，最好每10分钟将包换到另一侧肩膀或另一只手上，这能有效防止颈椎和脊椎劳损。

肩膀痛不妨做做伸展运动

背包时如果感觉到肩背疼痛，海迪·普拉瑟建议，最好立刻停下来做1分钟伸展运动，如果情况不允许，就把包从肩膀上拿下来，夹在腋下几分钟。

走路姿势要“正直”

背包设计 第3篇

假设, 物品数量为n个, 其重量为wi, 价值用vi (i=1, 2, ) 表示, 背包的最大承重量为W, 当物品i被选入背包时, 定义变量xi=1, 否则xi=0。现在对n个物品进行选择, 则背包内n个物品总重量为undefined, 物品的总价值为undefined, 即如何选择最佳的物品组合, 使背包里的物品总量既不超过W, 又使其价值最大。用数学模型表示如下:

undefined

式中, xi取值范围为0或者1, i=1, 2, , n。 0-1背包问题是组合优化领域经典的NP完全问题, 目前求解的算法的较多, 分为精确算法和近似算法, 精确算法的时间和空间复杂度较高, 而近似算法可以花较少代价求出问题的近似解。本文着重阐述求解0-1背包问题的两个经典算法。

20-1背包问题的求解算法

2.1动态规划算法 (Dynamic Programming)

动态规划算法是将待求解问题分解成多个子问题, 且每个子问题是相互关联和相互影响的。

2.1.1 动态规划算法设计

为了设计一个动态规划算法, 需要推导出一个递推关系, 用较小实例的解的形式来表示背包问题的实例的解。我们来考虑一个有前i个物品 (1in) 定义的实例, 物品的重量分别为w1, , wi、价值分别为v1, , vi, 背包的承重量为j (1jW) 。设V[i, j]为该最优解的物品总价值, 即能够放进承重量为j的背包中的前i个物品中最有价值子集的总价值。可以把这样子集分为两类:包括第i个物品的子集和不包括第i个物品的子集。可得:

(1) 在不包括第i个物品的子集中, 最优子集的价值为V[i, j]。

(2) 在包括第i个物品的子集中 (因此j-wi≥0) , 最优子集是由该物品和前i-1个物品中能够放进承重量为j-wi的背包的最优子集组成。这种最优子集的总价值等于vi+V[i-1, j-wi]

所以, 在前i个物品中最优解的总价值等于这两个价值中的较大者。当然, 如果第i个物品不能放进背包, 从前i个物品中选出的最优子集的总价值等于从前i-1个物品中选出的最优子集的总价值。因此, 得出如下递推式:

undefined

初始条件为, 当i≥0时, V[i, 0]=0;当j≥0时, V[0, j]=0。

我们的目标是求V[n, W], 即n个给定物品中能够放进承重量为W的背包的子集的最大总价值, 以及最优解本身。

2.1.2 算法实现

用C++语言实现算法, 代码如下:

cout<<"请输入物品的个数和背包的承重量"<

cin>>n>>maxw;

int *w=new int[n+1];

cout<<"请输入每件物品的重量"<

for (i=1;i<=n;i++)

cin>>w[i];

int *v=new int[n+1];

cout<<"请输入每件物品的价值"<

for (i=1;i<=n;i++)

cin>>v[i] ;

int **c;

c=new int *[n+1];

for (j=0;j<=n;n++)

c[j]=new int[maxw+1];

for (i=0;i<=n;i++)

for (j=0;j<=maxw;j++)

c[i][j]=0;

result=knapsack (n, maxw) ;

cout<<"最大总价值为"<

}

该算法的时间和空间复杂度都是O (n maxw) 。

2.2贪心算法 (Greedy Algorithm)

贪心算法是对求优解问题的一种更为简单和迅速的技术, 它总是对当前的问题作最好的选择, 也就是局部寻优。通过局部寻优最后得到整体最优。

贪心算法每次只考虑一步, 每一步数据的选取都必须满足局部最优条件。在枚举剩下的数据与当前已经选取的数据组合获得的解中, 提取其中能获得最优解的唯一的一个数据, 加入结果集合中, 直到剩下的数据不能再加入为止。

2.2.1 贪心算法设计

在使用贪心算法对0-1背包问题求解时, 可以采用一些策略, 使得到的解更接近最优解。具体方案如下:

(1) 价值最大者优先:从剩余物品中, 先选择价值最大的能够装入背包的物品, 然后再装入下一个价值最大的物品, 直到背包装不下剩余的物品为止。

(2) 重量最小者优先:先在剩余物品中把重量最小的物品装入背包中, 然后再继续选择剩下物品中重量最小的装入背包, 直到背包装不下剩下的物品为止。

(3) 单位价值最大者优先:根据价值 /重量的比值, 依次选取剩下的物品中比值最大的物品装入背包, 直到背包装不下剩下的物品为止。

通过对以上3种方案进行比较得出以下结论:

方案1:背包的承重量不能够得到有效利用。

方案2:重量小的物品价值不一定是最有价值的。

方案3:综合考虑了重量和价值, 该方案可能得到问题的最优解, 本文就讨论此方案。

方案3的具体步骤为:

第一步:计算每个物品的价值重量比ri=vi/wi, i=1, 2, , n。

第二步:按第一步计算出来的比率对物品非递增排序。

第三步:重复下面的操作, 直到有序列表中不留下物品。如果列表中的当前物品能够装入背包, 就将它放入背包中, 否则, 处理下一个物品。

2.2.2 算法实现

具体实现算法如下:

#include

using namespace std;

typedef struct{

int num, r;

}node;

void QuickSort (node *r, int s, int t) ;

void main ()

{

int n, maxw, i, x, y, z, value=0;

cout<<"请输入物品的个数和背包的承重量"<

cin>>n>>maxw;

int *w=new int[n+1];

cout<<"请输入每件物品的重量"<

for (i=1;i<=n;i++)

cin>>w[i];

int *v=new int[n+1];

cout<<"请输入每件物品的价值"<

for (i=1;i<=n;i++)

cin>>v[i] ;

node *r=new node[n+1];

for (i=1;i<=n;i++)

{

r[i].num=i;

r[i].r=v[i]/w[i];

}

QuickSort (r, 1, n) ;

z=maxw;

for (i=1;i<=n;i++)

{

x= r[i].num;

y=z;

if (y-w[x]>=0)

{

z=y-w[x]; value=value+v[x]; cout<

}

}

cout<

3算法分析与比较

通过对以上算法基本原理的介绍与分析, 我们认识了解决0-1背包问题的两种不同途径, 现在对这两种算法从时间、空间复杂度、准确性等性能方面进行进一步的分析比较, 得出它们之间的区别与联系。

3.1动态规划算法

动态规划算法的空间和时间复杂度由物品的数量和背包的承重量来决定, 设物品数量为n, 背包承重量为maxw, 初始化数组需要空间为O (n*maxw) , 两重for循环的时间复杂度为O (n*maxw) 。

由此可知, 动态规划算法对问题规模较大的问题求最优解速度慢, 空间消耗大, 它适合于规模很小问题求解, 但它能保证求解的正确性。

3.2贪心算法

贪心算法的核心是计算出每件物品的价值重量比率, 然后对比率非递减排序, 由于用到快速排序算法, 可以使算法的时间复杂度达到O (nlogn) 。然而贪心算法属于近似算法, 虽然速度快, 时间消耗少, 但不一定是最优解, 失了问题求解的正确性。

例如, 假设背包承重量为W (W>10kg) , 物品描述如表1。

按照贪心算法的策略, 会选择第一个物品, 不会再选择第二个物品, 但选第一个物品不是本问题的最优解, 选择第二个物品才是本问题的最优解, 这体现了该算法的局限性。

4结束语

目前, 0-1背包问题还没有找到完善的求最优解的方法, 现有的智能算法都只能在一定的范围内求解, 各种算法都有一定的局限性。如文中所说的动态规划算法属于精确算法, 该算法采用由下至上的方法从子问题的最优解一步一步地构造出整个问题的最优解, 但该算法缺乏整体考察能力, 只适用于规模较小的问题。贪心算法属于近似算法, 可以在多项式时间内求解, 但不能保证求得的是最优解。因此, 对于0-1背包问题, 一方面需要在已有算法理论的基础上继续研究, 不断地加以改进和完善;另一方面也希望能从其它学科的算法中获得启示, 研究出解决0-1背包问题的新算法。

参考文献

[1]田烽楠, 王于.求解0-1背包问题算法综述[J].软件导刊, 2009 (1) .

[2]王晓东.计算机算法设计与分析[M].北京:电子工业出版社, 2003.

[3]刘玉娟, 王相海.0-1背包问题的两种扩展形式及其解法[J].计算机应用, 2006 (10) .

一些项目――背包问题 第4篇

对于吃货来说，过年最幸福的事就是吃了，没有之一!

但是对于女生来说，卡路里(热量)是天敌啊!

资深美女湫湫深谙“胖来如山倒，胖去如抽丝”的道理，所以她希望你能帮忙制定一个食谱，能使她吃得开心的同时，不会制造太多的天敌，

当然，为了方便你制作食谱，湫湫给了你每日食物清单，上面描述了当天她想吃的每种食物能带给她的幸福程度，以及会增加的卡路里量。

Input

输入包含多组测试用例。

每组数据以一个整数n开始，表示每天的食物清单有n种食物。

接下来n行，每行两个整数a和b，其中a表示这种食物可以带给湫湫的幸福值(数值越大，越幸福)，b表示湫湫吃这种食物会吸收的卡路里量。

最后是一个整数m，表示湫湫一天吸收的卡路里不能超过m。

[Technical Specification]

1. 1 <= n <= 100

2. 0 <= a,b <= 100000

3. 1 <= m <= 100000

Output

对每份清单，输出一个整数，即满足卡路里吸收量的同时，湫湫可获得的最大幸福值，

Sample Input

33 37 79 91051 15 310 36 87 56

Sample Output

1020

一开始我还以为是贪心问题，但WA了几次后，从网上才知道是完全背包问题，直接用动规方程

dp[j]=max(dp[j],dp[j-w[i]]+v[i]);

其中w[i]为重量,v[i]为价值，如果不拿当前j重量的东西，则价值为dp[j]，如果拿了，则要放入剩下dp[j-w[i]]重量的背包里，并加上当前价值v[i]

背包是“健康炸弹” 第5篇

调查发现，由于需要装的东西较多，大包普遍受到人们的青睐，75%的人背的都是大包。从事IT行业的上班族和学生的背包最重。从背包习惯来说，采取右肩单肩背的人最多。

由于背包太重对健康造成损伤，早已不是什么新鲜事，全球似乎都在面临着“背包病”的威胁。有调查显示，由于背包太重导致出现“肩膀或后背酸痛”、“左右肩膀高低不平”等症状的人，已经占到70%以上。“背包病”这颗“健康炸弹”一旦爆炸，会给人的全身健康都带来一定的影响。

脖子酸、肩膀疼。长时间坐在电脑前又背大包的人，往往是肩颈酸痛、肩手麻木无力症状最突出的人群。背包过重会让脖子不自觉地倾向一边，一边肌肉拉伸，一边紧缩，这样很容易导致疼痛。其次，过重的背包还会让肩背部肌肉，如斜方肌和提肩胛肌长期受到压迫，可能出现慢性拉伤。

脊柱弯、驼背、脊柱侧弯、腰椎间盘突出、脊柱关节炎、坐骨神经疼痛等，都可能是背包过重惹的祸。专家指出，你在左肩背了一个5公斤左右的大包，那脊柱右侧的肌肉就要产生15至20公斤的力量，才能维持身体平衡，这种肌肉组织发力的不平衡会牵拉脊柱造成弯曲、劳损、发炎。此外，太重的包会导致椎间盘变性、下垂，压迫神经，引起坐骨神经痛。

手臂麻。很多女性喜欢将又大又沉的包挎在手臂上，老人买菜时也喜欢将装得满满的帆布袋用手拎着或挽着，时间长了，手臂或手腕很容易酸痛发麻。

臀部大腿关节劳损。很多人背着几十斤重的包长时间行走，负重大是膝关节磨损的一个高危因素。背包越重，膝关节的压力越大，容易产生关节问题，最终导致关节炎症。

把飞机装进背包 第6篇

在电视荧屏上,你总会看到无论美军跟哪个同盟国搞军演,士兵们背上都会背着鼓鼓囊囊的大背包,背包上方凸起一块形似网球筒一样的东西。如果你觉得那是一种新式背包,或者认为那些美军士兵包里装着网球,那你可就大错特错喽。其实它里面装的是一种微型侦察机。这种微型侦察机长约15厘米,旋转直径约12厘米,重约300克,机翼均为尼龙材料,可绕着机身卷起来。如此巴掌大的东西,放进背包肯定不成问题!

五脏俱全

你别小瞧这种微型无人机,它虽然小巧,但五脏俱全:发动机、速度表、接收机等等一应俱全。不同之处是它不用燃油,用锂电池驱动飞行。它可以在150米的高空飞行,时速可达80千米,只要电力充足可连续飞行1个小时。这种微型无人机只要一个弹射器弹出去,或者拿在手里投掷出去就可以飞行了。微型无人机上面装着微型摄像机,随时都能把所拍到的图片传到远方操作员的电脑设备上。

飞机小,用途大

这么小的微型飞机有什么作用呢?我们知道在现代化战争中,只有卫星和侦察机才能快速准确地搜集对方的情报,然而这些设备系统较为复杂,造价高,而且对山洞、房屋等小范围内的情报就难以搜集。所以要想在狭小空间里侦察敌情,这种微型无人机就派上了用场。

微型无人机有着不可替代的作用。除了普通飞行,微型无人机还具有慢飞、停立空中等特点,甚至可以贴着水面,它独特的本领特别适用于穿行在城市建筑间。它的式样不一而足,有的形如蝴蝶,有的形同蜻蜓,就因为它的样子跟昆虫别无二致,所以不宜被敌人察觉,这样它可以悄悄地进入敌方阵地窃取情报,或者投放微型爆炸装置。目前很多国家用它为侦察兵探路。在生活中,它的用途也很广,可以深入厂矿探测生化污染,在地震废墟中搜索幸存者,还可监视犯罪团伙的行踪。

个性十足

偶遇背包客 第7篇

他是我们在攀爬了一个多小时的崎岖而静谧的山路上唯一的 “偶遇”,我们欣喜地打量着他, 他约摸五十岁,应该是一位资深背包客。正当我们还在迟疑是否 “与陌生人说话”时,他已抢先用流利的长沙方言与我们熟络了, 只见他利索地挽起心爱的红色大背包,朗声说道“‘傣咖’ (大家) 同路上山吧!”于是,他成了我们的向导,大家一边攀谈相熟, 一边领略着山的伟岸、林的茂盛、 涧流飞瀑的欢腾……

他说他从繁华的省城而来,是一位经济分析师,每年他都会独自背包来到这里,在山顶的悬崖寺庙里住上几天,不图别的,只求安安静静地找回自己,畅畅快快地补益身心。

“望山累死马哟”,山路越走越累,当我们问他为何山顶寺看似很近,却又总是遥不可及时,他冒出了这么一句并提议稍作休息。 大家席地而坐,蝉鸣声也知趣地戛然而止,我和同伴都忙着喝水、吃零食,而他却从背包中“请”出了一本书,饶有兴致地独享起来,我轻轻地走过去,生怕打搅他的这份愉悦与宁静,却又十分好奇这是怎样的一本随着背包走天下的书,他自豪地微笑着将书递给我,说: “‘嘎’ (这) 是 《无诗不成唐》 呢,我喜欢看!”我小心翼翼地捧过书,轻轻地翻阅,感受到了一位背包客不一样的精神世界。我想, 也许这就是唐代风流才子般的超脱吧!

不一会儿,他便起身高吟到: “天生一个仙人‘庙’,无限风光在险峰啊!”此时,他的背包已娴熟地趴在了背上,散发出莫名的号召力,鼓舞着我们继续攀行,大家忘了腿脚的酸痛,毅然地向有着 “奇伟、瑰怪、非常之观”的山顶进发。

山路十八弯,蛇一般地缠绕着山脊向目标高地艰难地延伸。而他背上的行囊却丝毫不知疲倦地在我们眼前幸福地摇摆着,我的思绪也随之蹁跹……

他的行囊中满载着的,是不同于徐霞客“朝碧海而暮苍梧”的专业旅行,他无须设定专业方向去调查探究;也不同于众多归隐人士 “聊乘化以归尽”的离群索居,他无须为了逃避现实而深隐山中;更不同于一般人“到此一游”的旅行理念,他不屑于在游人众多的风景名胜前,摆出剪刀手,咔嚓一下发到朋友圈;也不同于“世界那么大,我想去看看”的辞职走天下的生活秀,他依然勤奋地打理着自己的事业,依然脚踏实地过着平凡的生活,他的背包之旅所追寻的,仅仅只是喧嚣和禁锢中的些许宁静和自由,这种背起背包、说走就走的冲动之旅,其实只是简单的自我对话、纯粹的心灵解放、多元的现代生活范儿……

一长排的山顶古寺建筑终于 “如约而至”,壮观迤逦的山顶风景顿时将我们迷住了。我与同伴只顾着兴奋地饱览美景,欣喜地自拍留影。而此时,这位偶遇的背包客已坐在香烟缭绕的佛楼前与道士老友开怀畅谈了,他那精神饱满的行囊,恰似回到了温馨的家,静静地幸福地在禅房木椅上酣然入眠……

旅行背包外挂式折叠座椅 第8篇

当人们到车站买票或办理其他业务时,常常需要排队等待很长时间,这对年纪较大、身体较弱的人来说,是件特别辛苦的事。即使是身体强壮的年轻人,长时间站立也会感到特别劳累。我设计的这种旅行背包内藏折叠座椅,可以很好地帮助人们解决这个的苦恼。小座凳不用时,通过尼龙搭扣固定在双间背包的底部;若需要坐下时,可随时从后面背包上取下(不用把背包从身上取下),打开折叠小凳后即可。小凳上有一根“防忘绳”连着背包,防止忘记收起小凳而丢失。

背包问题的差分进化算法 第9篇

关键词：背包问题,优化,差分进化算法

一、引言

背包问题 (Knapsack Problem) 是运筹学中一个典型的优化难题[1]，有着广泛的实际应用背景，如预算控制、项目选择、材料切割、货物装载等问题，并且还常常作为其他问题的子问题加以研究。背包问题的描述有多种形式，其中，一般的整数背包问题可在有界的前提下化成等价的0-1背包问题，本文这里仅考虑最基本的一维0-1背包问题。记ip, wi (i=1, 2, L, n) 分别为物品的价值和重量，V为总重量限制，变量

则问题模型可写成如下的0-1整数线性规划形式[2]：

从计算复杂性理论来看，背包问题是个NP-难题，是否存在多项式时间有效算法尚不可知。目前已有的求解方法分为精确算法 (如动态规划、回溯法、分支定界等指数级方法) 和

近似算法 (如贪心法、Lagrange法等) 两大类。下面将给出一种基于差分进化思想的新型算法，经大量计算试验，取得了一定的效果。

二、算法思想

差分进化算法[3] (Differential Evolution, DE) 是RainerSto rn和Kenneth Price于1995年共同提出的一种采用浮点矢量编码，在连续空间中进行启发式随机搜索的优化算法[4]近年来，差分进化算法作为一种性能卓越的优化算法正受到日益关注，其应用领域也越来越广。

为了将DE用于0-1背包问题.本文在进行初始化是对0-1变量，先在{0, 1}实数空间随机取值，然后采用四舍五入法进行取整运算[5]，得到对应的0-1变量，在变异操作时，对变异矢量同样采取四舍五入的方法进行取整，该方法扩大了寻优空间，有利于提高算法搜索到最优解的鲁棒性.。用随机产生的两个0-1背包问题对改进算法进行了测试，实验结果表明了所提出的改进DE (Modified DE, MDE) 算法用于求解0-1背包问题的有效性。

其中，目标函数f的形式已转化为:

(M为一充分大的正数) ，即把原约束方程作为罚函数项加入原目标函数中[2]。

三、改进的差分进化算法

1、变量描述与初始化

DE由N个参数矢量ixt (i=1, 2, , N, 其中t表示第t代) 构成种群，在搜索空间进行并行直接的寻优.设0-1变量的维数为D, ix可表示为 (x1i, x2i, ..., xDi) 初始化时，根据式 (3) 对0-1变量x进行初始化.对于0-1变量，先在{0, 1}实数空间进行随机取值，然后进行取整运算，得到对应的0-1变量.式中rand () 为[0, 1]之间的均匀随机数.xL和Ux分别为相应决策变量的下界和上界。

2、变异操作

(1) 0-1变量变异操作

DE最基本的变异成分是父代的差分矢量，每个矢量对包括父代两个不同的个体 (xtr1, xtr2) 根据变异个体的生成方法不同，形成了多种不同的差分进化算法方案[6]。其中本文用四舍五入的方法进行取整，对0-1变量进行变异操作的方程为

式 (4) 中xtr1, xtr2, xrt3为互不相同的随机个体，F∈[0, 2]，为缩放因子.变异矢量mx其实就是rx3t的一个噪音版本。

3、交叉操作

DE利用交叉操作以保持种群的多样性。对于群体中第i个个体ixt，将与mx进行交叉操作，产生试验个体Tx。为保证个体ixt的进化，首先通过随机选择，使得Tx至少有一位由mx贡献，而对于其他位，可利用一个交叉概率因子CR，决定Tx中哪位由mx贡献，哪位由ixt贡献.交叉操作的方程为

式 (5) 中rand () 为[0, 1]之间的均匀分布的随机数, CR∈[0, 1].由式 (6) 可知, 如果CR越大, 则mx对Tx的贡献越多, 当CR=1时, mx=Tx, 有利于局部搜索和加速收敛速率;如果CR越小, 则t ix对Tx的贡献越多, 当CR=0时, t ix对Tx, 有利于保持种群的多样性和全局搜索.由此可见, 在保持种群多样性与收敛速率之间是矛盾的.良好的搜索策略应该是在搜索的初始阶段保持种群多样性, 进行全局搜索, 尽可能得到多个可能全局最优的种子, 而在搜索的后期应加强局部搜索能力, 以提高算法的精度.基于这种思想, 本文采用指数递增交叉概率因子CR的方法, 即CR随迭代次数的增加而由小变大, 初始阶段t ix对Tx贡献多, 提高全局搜索能力, 而在后期则mx对Tx贡献多, 提高局部搜索能力.设CRm in为最小交叉概率, CRmax为最大交叉概率, t为当前迭代次数, Tmax为最大迭代次数, 则CR由方程 (6) 确定

其中参数a=30, b=3.

4、选择操作[7]

DE采用“贪婪”的搜索策略，经过变异与交叉操作后生成的试验个体Tx与ixt进行竞争，只有当Tx的适应度值较ixt更优时才被选作子代，否则，直接将ixt作为子代.选择操作的方程为： (6)

四、算法流程

综合以上对DE的改进，提出的求解0-1NLP的改进DE算法的流程如下：

Step 1.初始化种群规模NP，收缩因子F，交叉概率CRmin和CRmax.在{0, 1}实数空间内按式 (2) 随机初始化每一个个体.设置差分进化算法最大迭代次数Tmax，置当前迭代计数器t=0。

Step 2.计算每个个体每个约束条件的惩罚量。

Step 3.按式 (1) 计算每个个体的适应值，求出最优适应值及最优个体。

Step 4.判断是否达到罚函数法的终止条件，若是则退出，输出最优值.否则差分进化算法开始迭代，执行下一步。

Step 5.对ixt (i=1, 2，，N) 执行 (6) ～ (8) 步，生成第t+1代种群。

Step 6.在种群中随机选择三个与ixt不同的个体，按式 (3) 进行变异操作，生成变异个体mx。

Step 7.按式 (4) 和 (5) 进行交叉操作，生成试验个体xT。

Step 8.按式 (6) 进行选择操作，生成t+1代个体ixt+1。

Step 9.t=t+1，返回step2。

五、计算试验

我们从实验上将前述差分进化算法与背包问题的两个常用算法回溯法 (精确型) 和ε-近似法[1]进行了大量数值比较，各ip和iw在1～100内随机生成，V则选用两种形式[2]：

这里，给出两个数值算例及有关结果。其中，参数CRmin=0.1;CRmax=0.9;F=0.5。

[例1]n=10, V=269, W={95, 4, 60, 32, 23, 72, 80, 62, 65, 46}, P={55, 10, 47, 5, 4, 50, 8, 61, 85, 87}。

运行回溯法和ε-近似法可得到最优值295。运行本文的蚂蚁算法，8次迭代后，可得最优值，其平均收敛性态 (每种迭代次数下运行10轮) 如图1所示:

[例2]n=20, V=878, W={92, 4, 43, 83, 84, 68, 92, 82, 6, 44, 32, 18, 56, 83, 25, 96, 70, 48, 14, 58},

P={44, 46, 90, 72, 91, 40, 75, 35, 8, 54, 78, 40, 77, 15, 61, 17, 75, 29, 75, 63}。运行回溯法得最优值1024, 运行ε-近似法得近似值1018。运行本文的蚂蚁算法13次迭代后, 可得最优值, 在Pentium (R) 4 CPU 3.20GHz1.00GB内存, 操作系统windowsXPhome版本微机上耗时1秒左右, 其平均收敛性态 (每种迭代次数下运行10轮) 如图2所示:

在各迭代次数上的最好、最差和平均结果如下表所示:

此外，采用该算法陆续求解测试了一系列的随机算例，问题规模从n=10到n=100，算法收敛性态好，都能收敛与最优解。

六、结论

本文给出的求解算法，不仅可用于上述基本的背包问题，对整数形式的背包问题同样适用，更为重要的是，算法还能求解非线性形式的背包问题，这对已有的经典方法来说是无能为力的。当然，差分进化算法在本质属于随机型优化方法，其最大的弱点是计算时间较长，并行化实现是一个很好的出路。鉴于其基本的理论与应用研究现今还处于萌芽时期，更多深入细致的工作有待于进一步展开。

参考文献

[1]Syslo, M.M, et al.Discrete Optimization Algorithms[M].Englewood Cliffs, New Jersey:Prentice-Hall, 1983.118-165.

[2]马良、王龙德:《背包问题的蚂蚁优化算法》, 《计算机应用》, 2001, 21 (8) :4-5。

[3]Price K V.Differential evolution:A fast and simp le numericalop timizer[A].Proceedings of the1996Biennial Conference ofthe North American Fuzzy Information Processing Society[C].

[4]Storn R, P rice K.Differential evolution-a simple and efficient adaptive scheme for global op timization over continuous spaces[R].Technical Repo rt International Computer Science Insti2tute, Berk ley, 1995.

[5]吴亮红、王耀南、陈正龙:《求解混合整数非线性规划问题的改进差分进化算法》, 《小型微型计算机系统》, 2007, 19 (4) :92-95。

[6]袁亚湘、孙文瑜:《最优化理论与方法》, 科学出版社, 1997, 1。

背包客，出发！ 第10篇

今天，我们要认识的是川陵哥哥。1998年，他考入清华大学，后来他考取了奖学金去了新加坡国立大学计算机系读书。毕业后1年加入新加坡教育部，他很勤奋，还利用业余时间继续进修硕士和博士学位。10年时间内，他的足迹遍布6大洲71个国家。

旅行是他的传奇。

可以让我了解你与旅行的亲密关系吗?

川陵哥哥：我和所有的男孩一样，喜欢旅行、摄影、踢足球和下围棋。但是我比大部分男孩子更有勇气，20岁那年开始，我便一个人自费背包旅行，注意哦，是一个人!旅行仅仅是我的爱好之一，就好像你爱吃鸡翅膀，却不会因为爱吃鸡翅膀而感到骄傲一样。如果你也想踏上体验世界的路，无论是旅行、登山、潜水还是跳伞，都不要期待被理解或记得，自己开心就好啦!

那你的父母会放心让你单独旅行吗?

川陵哥哥：小时候家境不是很好，不过父母仍酷爱旅行，于是我跟着他们爱上了旅行。所以说家长的喜好对孩子的影响很大，家长要是喜欢打麻将，孩子也会有样学样呢!所以你要回去告诉父母：“你们要做好榜样哦!”小时候跟父母旅行时，妈妈老让我写游记，可我不想写，她就逼着我写。如今我写了这么多的游记，很多媒体还刊登我的游记，这和她的“强迫”是分不开的。

出国旅行四件法宝

1、旅行手册

孤独星球手册是一个系列手册，号称背包客的圣经，但不少国家的lonely planet写得问题百出，地图也常有错误。所以根据国家的不同，你可以认真选择不同的手册。

2、廉价航空廉价航空让我们坐飞机比坐火车和汽车便宜许多。例如从里斯本到伦敦，才花了我400多元人民币。希望廉价航空在亚洲尽快发展起来，这样我们去旅行就划得来多了。

3、背包客旅店

我曾在伦敦住过一间Rating No.1的背包客旅店，它紧靠地铁，距离市中心2－3站，一晚才10英镑。这家旅店有个超大的院子——游泳池那么大，院子中央是一栋3层的老式英国洋楼，里面完全是老式的木家具，还有非常干净的床铺，以及无线上网、免费地图和免费早餐。

4、国际学生证

你有学生证吧。我也有，不过我有的是国际学生证。有了它，我在全球各个公园可以享受20％到100％的折扣，有不少公园和博物馆凭借国际学生证可以免费进入。例如印度国家博物馆只收1卢比，西班牙塞韦利亚皇宫免费。

我的梦想就是：体验每一个国家。同学们愿意和我一起旅行吗?下次我带你们去非洲看企鹅!

什么非洲有企鹅?说错了吧?

关于0-1背包问题的研究 第11篇

背包问题是一种组合优化问题, 具有较强的实际意义, 从现实应用角度来看, 货物的装箱问题、物资的分配和存储问题等都可以用背包问题来解决。随着现代网络的日益发展, 在电子商务领域中, 背包公钥密码的应用也越来越广泛。但是当求解问题的数量较多时, 最优解的求解还是比较困难, 所以, 对0-1背包问题进行算法研究或改进是一件很有必要的工作。

传统求解背包问题的方法有近似算法和精确算法, 其中, 近似算法包括贪婪法、粒子群算法[1]、遗传算法、蚁群算法[2]等;精确算法包括回溯法、动态规划法等。精确算法存在空间及时间复杂性的问题, 为克服此缺点, 用近似算法求解背包问题已经越来越受到人们的关注。除了上述这几种常见的算法以外, 还出现了二进制差异演化算法[3]、知识进化算法[4]等新的算法。还有粗糙集也可以用于解决背包问题, 将粗糙集理论引入遗传算法来解决背包问题, 目的在于提高单纯遗传算法的搜索效率, 同时也可以改善解的质量。

1 0-1背包问题[5]

背包问题可以这样理解:假设一位商人有一个容量为C公斤的背包, 现在有n个重量和价值分别为ci>0和pi>0 (i=1, 2, …, n) 的物件, 选择哪几个物件放入背包, 能使所装物件的价值最大, 并且不超过背包的容量限制。

0-1背包问题是指每类物件都有一件放入或者不放入。设变量为xi, 当物件i被放入时, 则xi=1;不放入时, xi=0。其数学表达式为:

2 常规算法在求解0-1背包问题中的应用

2.1 近似算法

2.1.1 贪婪法

贪婪法属于一种启发式算法, 贪婪算法会以当前状况为基础作最优选择, 容易忽略整体, 但它可以在较短的时间内求到解, 在很多情况下可以达到预期的目的, 缺点是该启发式算法不一定能够获得最优解。

贪婪策略对贪婪法求取最优解至关重要, 常用的贪婪策略有质量贪婪准则和价值密度贪婪准则、价值贪婪准则。这3种贪婪策略对背包的装入都是采用多步过程来完成的。贪婪法可以与其他算法相结合来解决背包问题, 例如有杨婷婷、赵新超的更贪心粒子群算法, 对于大规模背包问题的求解非常有帮助;此外还有马杰良和刘茜提出的混合遗传算法[6], 贪婪算法可以为遗传进化过程打下良好的基础, 最终结果表明在求解质量及速度方面该算法都卓有成效。

2.1.2 遗传算法

遗传算法具有高效性、全局最优性和并行性的优点, 广泛应用于函数的优化过程中, 它把问题中每个可能性的解当成群体的一个染色体, 再对染色体进行编码, 依据目标函数进行个体评价, 得出适应值, 并依据适应值开始寻优, 其寻优过程由选择和杂交、变异步骤实现[7]。在此过程中, 选择算子及杂交算子影响寻优过程的搜索能力, 变异算子则决定了寻优过程中空间的每个点都能被搜索到, 因此该算法具有能够搜索全局最优解的优点。

采用传统的遗传算法解决背包问题时, 得到最优解或近似最优解的前提是背包问题的规模较小, 当背包问题的规模较大时, 会出现早熟的情况, 不会得出理想的结果, 需要进一步改进。改进的方法可以用罚函数法来对目标函数进行改造;还可以把贪心算法和遗传算法相结合, 贪心算法可以对染色体的解码过程进行改造, 即为混合遗传算法。

除此以外, 文献[8]把禁忌搜索算法和遗传算法相结合, 为背包问题的解决提供了新的思路, 该算法在父代种群的选择、杂交和变异操作基础上, 对产生的子代单独个体进行禁忌搜索, 搜索完成后, 该个体将会被邻域的最优解取代。当禁忌搜索完所有子代个体后, 就完成了新种群的衍生过程。其实验结果说明, 该算法在搜索效率及收敛速度上卓有成效。

另外文献[9]指出了主动进化遗传算法的思想, 这种算法在对种子个体进行编码时采用概率编码方法, 用定向变异方式代替了交叉操作, 可以使遗传算法的寻优过程更为有效和确定, 避免了传统遗传算法中由于是不定向变异而产生的盲目性。

2.1.3 蚁群算法

蚁群算法具有较强的鲁棒性和全局优化性, 并且该算法容易与其他优化算法相结合, 在车辆路径系统与通信系统等方面应用较为完善。在利用蚁群算法解决0-1背包问题时, 关键点在于某一物件聚集的信息素越多, 该物件就越有可能被选中。对应于0-1背包问题的物件取值0, 1, 利用蚁群算法时将一个变量设为两只蚂蚁, 并定义目标函数f为[10]:

其中:M为一充分大的正数。

蚁群算法应用于背包问题的具体过程可概括为首先要对迭代次数进行设置, 之后把各蚂蚁放在对应变量的0或1位置点, 然后依据转移概率对各蚂蚁进行移动, 依据强度更新方程对信息素的轨迹进行更新, 最后对当前最佳蚂蚁的位置点进行记录, 往复循环此过程直至达到退出条件。

一般情况下蚁群算法的收敛速度较快, 但当数据的数量增多时, 蚁群算法的收敛速度随数据规模的增大而降低。很多学者对该算法的缺点进行了改进, 在减少算法时间和降低寻优计算量方面做出了一定贡献。文献[11]提出了一种新的混合算法, 该方法使用蚁群算法得到优化解, 为扩大解的搜索空间使用了抗体克隆选择算法, 这种混合算法可以提高收敛的速度, 同时也在一定程度上增强了寻优的能力。文献[12]中把交换策略引入到蚁群算法中, 对不属于禁忌表的有向线段序号及属于禁忌表的有向线段序号进行交换, 该局部优化方法可改善每一代构造的解, 因此解的质量可以得到很好的改善, 使收敛速度明显加快。文献[13]提出一种新的基于解的相异度的蚁群算法, 这种算法把信息量放在物件上, 而非传统蚁群算法将信息量放在路径上, 同时该算法增加了信息量的局部更新机制, 如果一个物件被选中, 其信息量会马上减少, 从而降低其他蚂蚁选择该物件的可能性, 变异操作可以依据相异度适当地对变异概率进行调整。这种算法中解的变异概率是由解的相异程度决定的, 因此可以克服解的早熟现象, 无论是解的全局性还是解的多样性都得到了很大的改善, 特别适用于求解数量多、规模大的背包问题。

2.2 精确算法

2.2.1 动态规划法

在20世纪50年代, Richard Bellman提出了动态规划法, 这种方法可以将多阶段决策问题转换成一些相互关联的单阶段问题, 再对这些单阶段问题逐个解决。此方法可以较好地解决离散性问题, 其整体思路可概括为在把原问题分解成许多子问题的基础上, 通过每个子问题的求解最终得出原问题的解。

在所有背包问题的求解算法中, 动态规划算法被公认为是一种经典算法, 该算法具有便于实现及思路简单的优点, 但也有不足之处, 如果背包问题的数量较多、规模较大时此方法就有很大的局限, 维数过高, 复杂度大大增加, 存在维数障碍, 不易实现。

2.2.2 回溯法

回溯法中采用了深度优先的策略, 在整个解空间树中, 根结点作为始发点, 从这开始搜索整个解空间树, 结束时必须使根结点的每个子树都被搜索完成。在求解0-1背包问题时, 回溯法一定程度上可以得到最优解, 但当问题的数量较多时实现起来会比较困难。

可见, 当背包问题的规模较小时, 精确算法具有较强的实用性, 但当背包问题的规模不断增大时, 其计算复杂, 往往得不到最优解。

2.3 各种算法的分析与比较

通过上面的研究可知, 各算法都有优、缺点:①贪婪法速度较快, 但不足之处是不一定能获得最优解;②遗传算法能够获得近似最优解, 但可能会产生早熟的情况;③蚁群算法能够获得近似最优解, 但问题的规模较大时, 收敛速度不理想;④动态规划法能够获得最优解, 但求解过程速度较慢, 并且如果背包问题的数量较多时不宜实现;⑤回溯法能够获得最优解, 但时间的复杂度比较高, 背包问题的规模较大时实现比较困难。

因此, 上述各种算法的不足之处可以概括为两种:即最优解容易陷入局部最优;不能在较短的时间内求出全局最优解。

3 解决背包问题算法的发展方向

关于背包问题算法的发展过程, 从最早解决背包问题的精确算法, 到之后又产生的近似算法, 以及一些混合算法, 这些方法都卓有成效, 但依然有很多不足。未来背包问题算法的发展方向之一是将知识发现算法引入到传统的算法当中, 用知识发现算法挖掘背包问题中的主要信息。

在知识发现算法中, 粗糙集理论常用来解决一些不精确的问题, 适用于知识的分类及获取, 同时可以利用粗糙集理论的知识化简能力对知识系统进行化简, 减少属性及属性值, 降低属性项目复杂的计算程度。

用粗糙集理论来解决0-1背包问题的可能性是存在的, 可以使用粗糙集理论发现0-1背包问题中的主要物件, 在此基础上再利用遗传算法对它进行迭代运算。遗传算法在解决0-1背包问题时会产生大量数据, 使用粗糙集理论对数据进行化简、筛选和分析, 这样可以降低数据的复杂程度和维数, 使用提炼及概括后的数据会较容易发现遗传算法中的重要基因位, 可以避免遗传算法陷入局部最优解, 并在一定程度上改善遗传算法的搜索效率。