-背包问题求解方法综述

《-背包问题求解方法综述》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法分析与设计大作业实验题目：0-1背包问题求解方法综述组员：班　　级：指导老师：0-1背包问题求解方法综述【摘要】：0-1背包问题是一个经典的NP-hard组合优化问题，现实生活中的很多问题都可以以它为模型。本文首先对背包问题做了阐述，然后用蛮力解法、动态规划算法、贪心算法和回溯解法对背包问题进行求解，分析了0-1背包问题的数学模型,刻划了最优解的结构特征,建立了求最优值的递归关系式。最后对四种算法从不同角度进行了对比和总结。【关键词】：0-1背包问题；蛮力解法；动态规划算法；贪心算法；回溯解法。0.引言0-1背包问题是指给定n个物品,每个物品均有自己的价值vi和重量wi(i=1

2、,2,…,n),再给定一个背包,其容量为W。要求从n个物品中选出一部分物品装入背包,这部分物品的重量之和不超过背包的容量,且价值之和最大。单个物品要么装入,要么不装入。很多问题都可以抽象成该问题模型,如配载问题、物资调运[1]问题等,因此研究该问题具有较高的实际应用价值。目前,解决0-1背包问题的方法有很多,主要有动态规划法、回溯法、分支限界法、遗传算法、粒子群算法、人工鱼群算法、蚁群算法、模拟退火算法、蜂群算法、禁忌搜索算法等。其中动态规划、回溯法、分支限界法时间复杂性比较高,计算智能算法可能出现局部收敛,不一定能找出问题的最优解。文中在动态规划法的基础上进行了改进,提出一种求解

3、0-1背包问题的算法,该算法每一次执行总能得到问题的最优解,是确定性算法,算法的时间复杂性最坏可能为O(2n)。1.0-1背包问题描述0-1背包问题(KP01)是一个著名的组合优化问题。它应用在许多实际领域,如项目选择、资源分布、投资决策等。背包问题得名于如何选择最合适的物品放置于给定背包中。本文主要研究背包问题中最基础的0/1背包问题的一些解决方法。为解决背包问题，大量学者在过去的几十年中提出了很多解决方法。解决背包问题的算法有最优算法和启发式算法[2]，最优算法包括穷举法、动态规划法、分支定界法、图论法等，启发式算法包括贪心算法、遗传算法、蚁群算法、粒子算法等一些智能算法。0-

4、1背包问题一般描述为：给定n种物品和一个背包。物品i的重量是w(i)，其价值为v(i)，背包的容量为c。问应该如何选择装入背包的物品，使得装入背包中的物品的总价值最大？在选择装入背包的物品时，对每种物品i只有两种选择，即装入背包或不装入背包。不能将物品i装入背包多次，也不能只装入部分的物品i。因此，该问题称为0-1背包问题。此问题的形式化描述是，给定，要求找出一个n元0-1向量，使得，而且达到最大。数学模型：约束条件：，2.0-1背包问题的求解算法2.1蛮力算法（bruteforcemethod）2.1.1基本思想：对于有n种可选物品的0/1背包问题，其解空间由长度为n的0-1向量

5、组成,可用子集数表示。在搜索解空间树时，深度优先遍历，搜索每一个结点，无论是否可能产生最优解，都遍历至叶子结点，记录每次得到的装入总价值，然后记录遍历过的最大价值。2.1.2代码实现:#include#includeusingnamespacestd;#defineN100//最多可能物体数structgoods//物品结构体{intsign;//物品序号intw;//物品重量intp;//物品价值}a[N];boolm(goodsa,goodsb){return(a.p/a.w)>(b.p/b.w);}intmax(inta,intb){

6、returnan-1){if(bestP

7、stP;}intKnapSack1(intn,goodsa[],intC,intx[]){Force(0);returnbestP;}intmain(){goodsb[N];printf("物品种数n:");scanf("%d",&n);//输入物品种数printf("背包容量C:");scanf("%d",&C);//输入背包容量for(inti=0;i