购物单问题的回溯搜索算法分析与研究

《购物单问题的回溯搜索算法分析与研究》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、购物单问题的回溯搜索算法分析与研究李绵梁（陕西师范大学，西安，710062）摘要：购物单问题是一个典型的0-1背包问题。而0-1背包问题是算法分析设计中的经典问题，本文通过回溯搜索算法来解决购物单问题，并对该算法时间复杂度进行理论上和实际上的分析比较。关键词：购物单问题0-1背包回溯搜索一、问题描述：小明被评为省级三好学生，妈妈决定奖励他N元。小明就开始做预算，但是他想买的东西太多了，肯定会超过妈妈限定的N元。于是，他把每件物品规定了一个重要度，分为5等：用整数1~5表示，第5等最重要。他还从因特网上查到了每件物品的价格（都是整数元）

2、。他希望在不超过N元的前提下，使每件物品的价格和重要度的乘积的总和最大。设第j件物品的价格为v[j]，重要度为w[j]，共选中了k件物品，编号依次为j1，J2,…,jk,则所求总和为:V[j1]*w[j1]+v[j2]*w[j2]+…+v[jk]*w[jk]请你帮小明设计一个满足要求的购物单。二、算法分析与数学建模：假设：所买的东西都是独立的，即没有相互间的依赖关系。则对于每一件物品而言，只有买或不买两种情况，而物体本身也不可分，并且所买物体总数受总钱数所限，目标为所求重要性[1]尽可能大。因此，该问题是一个典型的0/1背包问题！推广

3、到一般，对于n件物品，假设对其进行依次编号1，2，3，…，n，不妨将第i件物品购买状况记为f[i](f[i]=0,1),即将购买第i件物品记为f[i]=1，不购买记为f[i]=0，则通过分析不难得出，该问题的数学模型为：1.重要性：本文定义为物体重要度与价格的乘积。从算法复杂性理论来看，该问题是一个NP问题。而目前，对该类问题的解决方法也是非常多的，主要包括分支限界法、群举法、图论法、贪心算法、蚁群算法等。本文作者用回溯搜索算法对问题进行求解与分析讨论。在题目约束条件（总价格不超过N元）的前提下，对问题解空间构成的树进行回溯搜索。在遍

4、历过程中，只有当前物品需要购买时（值为1），才需要进行购买后价格是否超过总N元的判断，若不超过，才需要进行更深的搜索；若判断购买后总价格大于N元，则无需进行更深的搜索。一、算法实现在算法实现过程中需要增加辅助变量如下：记录物品重要性、价格分别为数组w[]、v[]；记录总钱数为tm。在每次搜索过程中，记录当前搜索结果的当前最大重要性、当前花费钱数分别为cmax、total，当前最大重要性下对物品的取舍情况t[]；记录每次搜索对物品的取舍状态数组sign[]；设计回溯搜索的核心算法如下：voidwww(inti)//从第i层开始;{int

5、j;floatsum=0;//当前分支重要性总和if(i==n+1)//到达叶结点{for(j=0;jcmax){cmax=sum;//更改重要性for(j=0;j

6、otal+=v[i-1];www(i+1);sign[i-1]=0;total-=v[i-1];//回溯之前清理现场;}}一、算法复杂度分析1.理论分析在搜索过程中，对于不同的N，算法进行搜索的情况都不同。但该算法需要搜索的问题解空间共有2n个分支，因此，算法时间复杂度为O(2n)。2.实际分析对实验进行统计，其统计结果如表一所示：表一：实际实验时间复杂度数量n2345678时间t11.858771.883872.162172.445373.158225.594057.94152时间t21.690441.817022.108722.3

7、73603.127125.569218.35889时间t31.642331.885122.110972.227273.154795.618487.82389时间t41.648582.001362.035372.328613.140165.615887.76655时间t51.680781.928252.041902.339033.0375.762247.79614平均时间1.704181.9031242.0918262.3426863.1234585.6319727.9373983.理论与实际的比较对理论情况与实际实验情况的结果进行对比

8、，其时间复杂度图一所示。图一：理论与实际时间复杂度对比图由以上图示可以看出，实验理论时间复杂度与实际复杂度结果近似相似，因此可以说明该算法是正确的。一、结论0/1背包问题有许多算法，本文作者只是用回溯搜索算法对问题进行解