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

购物单问题的回溯搜索算法分析与研究李绵梁（陕西师范大学，西安，710062）摘要：购物单问题是一个典型的0-1背包问题。而0-1背包问题是算法分析设计中的经典问题，本文通过回溯搜索算法来解决购物单问题，并对该算法时间复杂度进行理论上和实际上的分析比较。关键词：购物单问题 0-1背包 回溯搜索一、 问题描述：小明被评为省级三好学生，妈妈决定奖励他N元。小明就开始做预算，但是他想买的东西太多了，肯定会超过妈妈限定的N元。于是，他把每件物品规定了一个重要度，分为5等：用整数15表示，第5等最重要。他还从因特网上查到了每件物品的价格（都是整数元）。他希望在不超过N元的前提下，使每件物品的价格和重要度的乘积的总和最大。设第j件物品的价格为vj，重要度为wj，共选中了k件物品，编号依次为j1，J2,jk,则所求总和为:Vj1*wj1+vj2*wj2+vjk*wjk请你帮小明设计一个满足要求的购物单。二、 算法分析与数学建模：假设：所买的东西都是独立的，即没有相互间的依赖关系。则对于每一件物品而言，只有买或不买两种情况，而物体本身也不可分，并且所买物体总数受总钱数所限，目标为所求重要性1尽可能大。因此，该问题是一个典型的0/1 背包问题！推广到一般，对于n件物品，假设对其进行依次编号1，2，3，n，不妨将第i件物品购买状况记为fi(fi=0,1),即将购买第i件物品记为fi=1，不购买记为fi=0，则通过分析不难得出，该问题的数学模型为：1. 重要性：本文定义为物体重要度与价格的乘积。从算法复杂性理论来看，该问题是一个NP问题。而目前，对该类问题的解决方法也是非常多的，主要包括分支限界法、群举法、图论法、贪心算法、蚁群算法等。本文作者用回溯搜索算法对问题进行求解与分析讨论。在题目约束条件（总价格不超过N元）的前提下，对问题解空间构成的树进行回溯搜索。在遍历过程中，只有当前物品需要购买时（值为1），才需要进行购买后价格是否超过总N元的判断，若不超过，才需要进行更深的搜索；若判断购买后总价格大于N元，则无需进行更深的搜索。三、 算法实现在算法实现过程中需要增加辅助变量如下：记录物品重要性、价格分别为数组w、v；记录总钱数为tm。在每次搜索过程中，记录当前搜索结果的当前最大重要性、当前花费钱数分别为cmax、total，当前最大重要性下对物品的取舍情况t；记录每次搜索对物品的取舍状态数组sign；设计回溯搜索的核心算法如下：void www(int i) / 从第i层开始;int j;float sum=0; / 当前分支重要性总和if (i=n+1) / 到达叶结点for (j=0;jcmax) cmax=sum; / 更改重要性for (j=0;jn;j+)tj=signj;return; signi-1=0; / 未到叶节点，不买第i件物品时;www(i+1);if (total+vi-1=tm) / 可买第i件物品的情况;signi-1=1;total+=vi-1;www(i+1);signi-1=0;total-=vi-1;/ 回溯之前清理现场;四、 算法复杂度分析1. 理论分析在搜索过程中，对于不同的N，算法进行搜索的情况都不同。但该算法需要搜索的问题解空间共有2n个分支，因此，算法时间复杂度为O(2n)。2. 实际分析对实验进行统计，其统计结果如表一所示：表一：实际实验时间复杂度数量n2345678时间t11.858771.883872.162172.445373.158225.594057.94152时间t21.690441.817022.108722.373603.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. 理论与实际的比较对理论情况与实际实验情况的结果进行对比，其时间复杂度图一所示。图一：理论与实际时间复杂度对比图由以上图示可以看出，实验理论时间复杂度与实际复杂度结果近似相似，因此可以说明该算法是正确的。五、 结论0/1背包问题有许多算法，本文作者只是用回溯搜索算法对问题进行解决，并根据实际实验复杂度与理论实验复杂度进行详细比较，来判断讨论出实际算法的正确性。本文只是用一种算法对问题进行解决是很局限的，也未能