背包问题(1)

                  小组成员：张灿、吴雪涛、高坤、占强、习慧平

小组分工情况

1、背包问题的历史由来

      它是在1978年由Merkel和Hellman提出的。它的主要思路是假定某人拥有大量物品，重量各不同。此人通过秘密地选择一部分物品并将它们放到背包中来加密消息。背包中的物品中重量是公开的，所有可能的物品也是公开的，但背包中的物品是保密的。附加一定的条件，给出重量，而要列出可能的物品，在计算上是不可实现的。背包问题是熟知的不可计算问题，背包以其加密，解密速度快而其人注目。在解决大量的复杂组合优化问题时，它常常作为一个子问题出现，从实际的观点看，许多问题可以用背包问题来描述，如装箱问题，货仓装载，预算控制，存储分配，项目选择决策等，都是典型的应用例子。随着网络技术的不断发展，背包公钥密码在电子商务中的公钥设计中也起着重要的作用。然而当问题的规模较大时，得到最优解是极其困难的。 但是，大多数一次背包均被破译了，因此现在很少有人使用它。

2、背包问题的描述

背包问题(Knapsack problem)是一种组合优化的NP完全问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。 　　相似问题经常出现在商业、组合数学，计算复杂性理论、密码学和应用数学等领域中。 　　也可以将背包问题描述为决定性问题，即在总重量不超过W的前提下，总价值是否能达到V？

3、背包问题的定义

我们有n种物品，物品j的重量为wj，价格为pj。我们假定所有物品的重量和价格都是非负的。背包所能承受的最大重量为W。如果限定每种物品只能选择0个或1个，则问题称为0-1背包问题。可以用公式表示为：

maximize 

subject to 

如果限定物品j最多只能选择bj个，则问题称为有界背包问题。可以用公式表示为：

maximize 

subject to 

如果不限定每种物品的数量，则问题称为无界背包问题。

4、背包问题的研究现状

    Dantzing在 20 世纪50 年代首先进行了开创性的研究，利用贪婪算法求得了0-1背包问题最优解的上界。1974 年，horowitz 和 salmi利用分支限界法解答背包问题，并提出了背包问题的可分性，指出了求解该问题的一条新途径。随后，balas 和 zemel 提出了背包问题的“核”思想，使背包问题的研究获得了较大进展。上世纪九十年代以后，随着生物仿生技术和网络技术的飞速发展，各种模拟生物物理规律的并行近似算法不断涌现，例如遗传算法己经在0/1背包问题上得到较好的应用，蚂蚁算法、粒子群算法等仿生算法也在组合优化问题

中得到了很好的应用。

5、求解0-1背包问题常见方法

  传统求解该问题的方法可以概括为精确算法和近似算法，其中精确算法有动态规划法、回溯法、分支限界法等，近似算法有遗传算法、贪婪法、 粒子群算法、蚁群算法等,由于精确算法的时间复杂性和空间复杂性等缺点， 近年来利用近似算法求解背包问题成为重点。

5.1精确算法

     5.1.1回溯法

     回溯法的基本思想是在包含问题的所有解的解空间树中,按照深度优先的策略,从根结点出发搜索解空间树，其用来求问题的所有解时,要回溯到根,且根结点的所有子树都已被搜索遍才结束。 用回溯法求解 0-1 背包问题是按照物品的单位价值从大到小排序,计算当前节点的上界,搜索左子树。只有当右子树包含可行解时才搜索右子树。剪去右子树的条件是当前价值加上剩余物品的总价值小于当前的最优总价值时,不需搜索右子树,可将右子树剪去。回溯法用一定的剪枝进行优化,算法的时间复杂度为 o(n2n), n为物品个数。 

  5.1.2动态规划法

   动态规划法是上世纪 50年代Richard Bellman创建的解决多阶段决策过程最优化的一种数学方法，即把多阶段决策问题变换为一系列相互联系单阶段问题，然后逐个加以解决。它的特点是解决多阶段、离散性问题。动态规划算法的基本思想是把原问题分解成一系列子问题,然后从这些子问题中求出原问题的解。 对一个负重能力为 C 的背包,如果选择装入第 i 种物品,那么原背包问题就转化为负重能力为 C-ci的子背包问题。动态规划算法是一种经典的背包问题求解算法，其原理简单，算法思路清晰，易于实现。动态规划算法虽然高效，但是对于规模较大的问题它不是一个理想的算法，主要原因就是它的维数障碍，即计算和存储量的需要对于状态空间和决策空间的维数的增长呈指数增长关系。动态规划算法的时间复杂度为 o(min(n·C，2^n)),其中 n 为物体的个数,C为背包负重。 

     精确算法的优点是当问题规模较小时一定可以求得最优解， 缺点是当问题规模较大时因计算量太大而无法实现。 所以一些学者提出了各种近似算法来解决精确算法求解背包问题时的时间复杂性和空间复杂性难题。

5.2近似算法

   5.2.1贪婪算法

      贪婪算法是一种逐步构造最优解的启发式算法， 其基本思想是在每一阶段它都在一定的规则下构造出当前看似最优的一个决策，决策一旦做出就不再更改。贪婪算法常以当前情况为基础作最优选择，而不考虑整体情况，所以贪婪法一般可以快速得到满意的解，因为它省去了为找最优解要穷尽所有可能而必须耗费的大量时间。虽然这种启发式的策略并不一定能够获得最优解,然而在许多情况下确能达到预期的目的。贪婪算法解决优化问题的最关键问题是制定贪婪策略。对于背包问题来说，贪婪的策略有常用的3种。它们是价值贪婪准则、质量贪婪准则和价值密度贪婪准则。每种贪婪策略都采用多步过程来完成背包的装入。在每一步过程中利用贪婪准则选择一个物品装入背包。其中采用价值密度(价值重量比 pi/ci)的贪婪准则是从剩余物品中选择可以放入背包的 pi/ci值最大的物品，直到超出背包容量装不下为止，并将未装入背包的物品编码修正为 0。算法的时间复杂度为 o(nlogn)。这种策略对于连续背包问题可保证得到最优解，但对于 0／1背包问题不一定能得到最优解。因此出现了一些对于贪婪算法的改进方法，例如文献中提出的算法在不增加时间复杂度的基础上， 保证求解质量较稳定地优于价值密度贪婪算法及价值密度改进算法。近年来还产生了贪婪法与其他算法结合的混合算法，有赵新超，杨婷婷提出的更贪心粒子群算法 ,  该算法对超过背包重量的粒子的处理方法是去掉已经装进去且性价比最差的物品，直到满足重量约束条件为止，这样在改善粒子质量的同时避免了罚函数方法中敏感的参数选择问题； 对于可行粒子的处理措施是将还未装入背包且性价比最好的物品装进背包，直到不能装为止。结果表明更贪心粒子群算法无论在寻优能力、计算速度和稳定性方面都有很好的表现，非常适合于求解大规模背包问题。还有刘茜、马杰良提出的混合遗传算法，它针对遗传操作交叉和变异的过程中不符合约束条件的个体，在解码过程中引入贪婪算法优先装入价值重量比大且物品标记为1 的物品， 直至背包容量装不下为止，通过引进贪婪算法使得遗传进化过程以良好的种子为基础进行，此外算法在变异操作和进化终止条件的设计上也进行了改进， 结果表明该算法在解的质量和求解速度方面都比遗传算法有很大的改良。

5.2.2蚁群算法

蚁群算法是由意大利学者 Dorigo M.等提出的一类模拟蚂蚁群体觅食行为的仿生优化算法。算法的基本思想是蚂蚁将根据信息素的多少选择走哪一条路，蚂蚁在觅食过程中会留下一种称为信息素的物质，若蚂蚁从巢穴到食物源所走的路径较短，则该蚂蚁从巢穴到食物源后再返回巢穴的时间也就较短，这样同时间内在较短路径上蚂蚁分泌的信息素就会较多。后面的蚂蚁将根据其他蚂蚁留下来信息素的多少而选择路径，某一条路径上的信息素越多，则这条路径被选择的概率越大。蚂蚁群体的这种集体行为构成了一种学习信息的正反馈机制，蚂蚁之间通过信息素来交流信息。蚁群算法模拟了这种优化机制，通过个体之间的信息交流与协作来寻找最优解。蚁群算法现已成功运用在 TSP、图像处理、车辆路径系统、通信系统等领域。它具有较强的鲁棒性、分布性、全局优化性和易与其它优化算法融合的优点,现已是解决 NP-hard问题的一个有效工具。  蚁群算法解决 0/1 背包问题的核心是：在某一物品上聚集的信息素越多，则该物品被选择的概率就越大。

背包问题的蚁群算法求解过程是：①设置迭代次数；②将各蚂蚁置于相应变量的 0、1位置点； 按转移概率移动各蚂蚁； 按强度更新方程更新信息素轨迹； 记录当前最佳蚂蚁位置；③  返回步骤②循环直到满足退出条件。 就蚁群算法而言当处理的数据比较小时其具有很快的收敛速度， 而随着数据规模的增大算法的收敛速度明显降低。蚁群算法在减少寻优计算量和缩短算法运行时间方面，有待进一步改进。针对蚁群算法的缺点，许多学者对蚁群算法进行了改进。 赵朝卿，胡小兵等提出了一种求解 0-1背包问题的混合型算法(KPAICACA)

，先利用蚁群算法求优化解，然后利用抗体克隆选择算法扩大解的搜索空间，使得在收敛速度和寻优能力两方面都有明显改善。具体方法是：每个物品 i的属性有重量 ci，价值 pi和信息素 τi，即信息素积累在物品上。选择物品 i的期望度为 ηi=pi/ci。每只蚂蚁都附一个背包和一个禁忌表， 蚂蚁将根据选中物品的重量来决定是否将其装入背包。 若物品装入背包而不超过其容量，则继续选择下一个物品；否则将其编号放入禁忌表中，以后选择物品时不再考虑。经过 n

次选择，构建了一个由物品编号表示的解，当 m 只蚂蚁都构建了自己的解，将这些编号解变换为 0-1 序列解，每个序列解被视做一个抗体，抗体编码的长度为 n，抗体群的规模等于蚂蚁种群的规模 m。随后对抗体群进行克隆、变异和选择操作。抗体免疫克隆算法搜索完成后，根据背包中物品的价值总和 P，记录最优解以及对应的物品价值总和，并对物品上的信息素进行更新。

  5.2.3遗传算法  

   遗传算法己被广泛地应用组合优化领域,其全局最优性、可并行性、高效性在函数优化中得到了广泛地应用 。遗传算法是将问题的每一个可能性解看作是群体中的一个个体(染色体),并将每一个染色体编码成串的形式,再根据预定的目标函数对每个个体进行评价,给出一个适应值。算法将根据适应度值进行它的寻优过程,遗传算法的寻优过程是通过选择、杂交和变异等遗传算子来具体实现的。它的搜索能力由选择算子和杂交算子决定,变异算子则保证了算法能够搜索到问题空间的每一个点,从而使其具有搜索全局最优的能力。遗传算法的时间复杂度为 O(T* n^2),其中 T为迭代次数，n为种群个数。运用简单的遗传算法（SGA，Simple  Genetic Algorithm）求解背包问题时若问题规模不大也能够得到最优解或近似最优解，但当规模较大时，算法容易早熟，得不到比较理想的结果，所以需要对其进行改进。遗传算法解决背包问题处理约束条件的方法有两种一种方法是用罚函数法改造目标函数；另一种方法是结合贪心算法改造染色体的解码过程。其中将遗传算法与贪心算法结合，实际上是一种混合遗传算法。 

6、几种常用算法的比较

   从表中看出，以上各种算法都有其自身的不足，大体分为两类问题：一是不能在有限时间内求出解，二是陷入局部最优。

7、0/1背包问题的展望

   由于精确算法的时间复杂性和空间复杂性等缺点， 近年来利用近似算法求解背包问题成为重点，出现了很多的新的算法。下面介绍几种。

     DNA计算， 是基于生化反应的一种全新的计算模式。 石晓龙等就一个 NP完全问题 （0-1背包问题）设计了一种基于 DNA链长度映射背包物品重量权值的一类带权值型组合优化问题的 DNA 分子计算方法。 该算法目的是用 DNA 分子计算模式解决带有数值运算特征的组合优化问题。DNA计算的时间复杂度为 o(n^2)。 

    知识进化算法是在分析知识进化机制基础上提出的一种可以解决复杂问题的新型优化方法，能广泛用于解决函数优化和组合优化问题。马慧民等根据0-1背包问题的特点，提出用于求该问题的知识进化算法方案，实现了算法并取得了良好的结果。  

    差异演化算法(DE)是一种基于群体差异的演化算法，是 Rainer Storn 和 Kenneth Prince在 1995 年提出的，属于直接搜索算法。该算法具有收敛速度快、操作简单，易编程实现，极强的稳健性等优点。传统差异演化算法的研究及应用主要集中在连续搜索空间的问题上，对于 0-1背包问题无法对其进行求解。蔡鸿英等通过采用新的变异方法，提出一种新的采用二进制编码技术处理的差异演化算法，阐明了该算法求解背包问题的具体实现过程。通过多个0-1 背包问题进行仿真，结果证明该算法在解0-1背包问题时能达到最优解且收敛速度较快。但是差异演化算法的收敛性、理论依据等还不完善，有待进一步研究。 

八：附录

动态规划求解01背包问题源程序及运行结果：

#include

#include

#define  N 100

using namespace std;

int n,weight,p[N],w[N];

void ReadData()

{

    ifstream ifs("a.txt",ios::in);

ifs>>n>>weight;

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

{ifs>>w[i]>>p[i];}

}

int cishu=0;

void Package()

{

    int sp,sw,cw=weight;

    int m[N][N];

for (int i=0;i<=weight;i++)

        if(i>=w[n])m[n][i]=p[n];

        else

            m[n][i]=0;

        for (i=n-1;i>=1;i--)

        {

for (int j=0;j<=weight;j++)

            {

                if(j>=w[i]&&m[i+1][j]                {m[i][j]=m[i+1][j-w[i]]+p[i];cishu++;}

                else

                    m[i][j]=m[i+1][j];

            }

        }

       cout<<"背包所装物品:"< cout<<"i "<<"w(i) "<<"p(i) "< for (sw=0,sp=0,i=1;i<=n-1;i++)

       {

           if (m[i][cw]>m[i+1][cw])

           {

               cw-=w[i];sw+=w[i];sp+=p[i];

               cout<           }

       }

       if (m[1][weight]-sp==p[n])

       {

           sw+=w[n];sp+=p[n];

           cout<       }

cout<<"w="<}

程序给出的测试用数据：

运行结果如下：

回溯法求解01背包问题源程序及运行结果：

#include

#include

using namespace std;

int path_num=1;

const int n=6;//物品数量

double c;//容量

double bestprice;

double currentprice;

double bestweight;

double currentweight;

bool bestchoice[n];//选择

bool currentchoice[n];

struct node

{

    double weight;

    double value;

}data[6];

void init()//初始化

{    c=60;

    data[0].weight=15;    

    data[1].weight=17;    

    data[2].weight=20;

    data[3].weight=12;

    data[4].weight=9;

    data[5].weight=14;

    data[0].value=32;

    data[1].value=37;    

    data[2].value=46;

    data[3].value=26;

    data[4].value=21;

    data[5].value=30;

    bestprice =0 ;

    currentprice = 0;

    currentweight = 0;

    memset(currentchoice,false,sizeof(currentchoice));

cout<}

int cishu=0;

void track(int k)//k = 0  1  2层   回溯搜索

{

if(k>=n)

    {

        if(currentprice > bestprice)

        {

            bestprice = currentprice;

            bestweight = currentweight;

            cishu++;

            for(int i=0;i            {bestchoice[i] = currentchoice[i];    

            cishu++;

            }

        }

        return;

    }

if(currentweight + data[k].weight <= c)//选择

    {

        currentweight +=data[k].weight;

        currentprice +=data[k].value;

        currentchoice[k] = true;

        track(k+1);

        currentweight -=data[k].weight;

        currentprice -=data[k].value;

        currentchoice[k] = false;

        cishu++;

    }

    {    track(k+1);}

}

void show_result()//显示结果

{

    cout<<"求出背包最大价值:    "<    cout<<"此时背包的重量:    "<    cout<<"此时的选择为:     ";

for(int i=0;i cout<    cout< for( i=0;i    if(bestchoice[i]==1)

    {cout<<"选择第"<        cout<        cout<<"模拟时间复杂度："<}

int main()

{   init();

    track(0);

    show_result();

    return 0;

}

程序运行结果：