0/1背包问题 蛮力/动规/回溯/分支定界

一、题目 ：

分别用蛮力法、动态规划法、回溯法和分支限界法求解0/1背包问题。

注：0/1背包问题：给定种物品和一个容量为的背包，物品的重量是，其价值为，背包问题是如何使选择装入背包内的物品，使得装入背包中的物品的总价值最大。其中，每种物品只有全部装入背包或不装入背包两种选择。

二、所用算法的基本思想及复杂度分析：

1.蛮力法求解0/1背包问题：

1）基本思想：

对于有n种可选物品的0/1背包问题，其解空间由长度为n的0-1向量组成,可用子集数表示。在搜索解空间树时，深度优先遍历，搜索每一个结点，无论是否可能产生最优解，都遍历至叶子结点，记录每次得到的装入总价值，然后记录遍历过的最大价值。

2）代码:

#include<iostream>

#include<algorithm>

using namespace std;

#define N 100 //最多可能物体数

struct goods  //物品结构体

{

    int sign;  //物品序号

    int w; //物品重量

    int p; //物品价值

}a[N];

bool m(goods a,goods b)

{

    return (a.p/a.w)>(b.p/b.w);

}

int max(int a,int b)

{

    return a<b?b:a;

}

int n,C,bestP=0,cp=0,cw=0;

int X[N],cx[N];

/*蛮力法求解0/1背包问题*/

int Force(int i)

{

    if(i>n-1){

       if(bestP<cp&&cw+a[i].w<=C){

           for (int k=0;k<n;k++)    X[k]=cx[k];//存储最优路径

           bestP=cp;

       }

       return bestP;

    }

    cw=cw+a[i].w;

    cp=cp+a[i].p;

    cx[i]=1;   //装入背包

    Force(i+1);

    cw=cw-a[i].w;

    cp=cp-a[i].p;

    cx[i]=0;   //不装入背包

    Force(i+1);

    return bestP;

}

int KnapSack1(int n,goodsa[],int C,int x[])

{

    Force(0);

    return bestP;

}

int main()

{

    goods b[N];

    printf("物品种数n: ");

    scanf("%d",&n);   //输入物品种数

    printf("背包容量C: ");

    scanf("%d",&C);   //输入背包容量

    for (int i=0;i<n;i++)    //输入物品i的重量w及其价值v

    {

       printf("物品%d的重量w[%d]及其价值v[%d]:  ",i+1,i+1,i+1);

       scanf("%d%d",&a[i].w,&a[i].p);

       b[i]=a[i];

    }

    int sum1=KnapSack1(n,a,C,X);//调用蛮力法求0/1背包问题

    printf("蛮力法求解0/1背包问题:\nX=[ ");

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

       cout<<X[i]<<" ";//输出所求X[n]矩阵

    printf("]  装入总价值%d\n",sum1);

    bestP=0,cp=0,cw=0;//恢复初始化

}

3）复杂度分析：

蛮力法求解0/1背包问题的时间复杂度为：2^n

2.动态规划法求解0/1背包问题：

1）基本思想：

令表示在前个物品中能够装入容量为的背包中的物品的最大值，则可以得到如下动态函数：

           

按照下述方法来划分阶段：第一阶段，只装入前1个物品，确定在各种情况下的背包能够得到的最大价值；第二阶段，只装入前2个物品，确定在各种情况下的背包能够得到的最大价值；以此类推，直到第个阶段。最后，便是在容量为的背包中装入个物品时取得的最大价值。

   2）代码：

    #include<iostream>

    #include<algorithm>

    usingnamespace std;

    #defineN 100   //最多可能物体数

    structgoods    //物品结构体

    {

        int sign;   //物品序号

        int w;  //物品重量

        int p;  //物品价值

    }a[N];

    boolm(goods a,goods b)

    {

      return (a.p/a.w)>(b.p/b.w);

    }

    intmax(int a,int b)

    {

        return a<b?b:a;

    }

    intn,C,bestP=0,cp=0,cw=0;

    intX[N],cx[N];

    intKnapSack2(int n,goods a[],int C,int x[])

    {

        int V[N][10*N];

        for(int i=0;i<=n;i++)   //初始化第0列

            V[i][0]=0;

        for(int j=0;j<=C;j++)   //初始化第0行

            V[0][j]=0;

         for(i=1;i<=n;i++)      //计算第i行，进行第i次迭代

            for(j=1;j<=C;j++)

                if(j<a[i-1].w)

                     V[i][j]=V[i-1][j];

                else

                   V[i][j]=max(V[i-1][j],V[i-1][j-a[i-1].w]+a[i-1].p);

                j=C;    //求装入背包的物品

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

                {

                    if (V[i][j]>V[i-1][j]){

                        x[i-1]=1;

                        j=j-a[i-1].w;

                    }

                    else    x[i-1]=0;

                }

                return V[n][C]; //返回背包取得的最大价值

     }

    int main()

    {

        goods b[N];

        printf("物品种数n: ");

        scanf("%d",&n); //输入物品种数

        printf("背包容量C: ");

        scanf("%d",&C); //输入背包容量

        for (int i=0;i<n;i++)   //输入物品i的重量w及其价值v

        {

            printf("物品%d的重量w[%d]及其价值v[%d]:  ",i+1,i+1,i+1);

            scanf("%d%d",&a[i].w,&a[i].p);

            b[i]=a[i];

         }

     intsum2=KnapSack2(n,a,C,X);//调用动态规划法求0/1背包问题

         printf("动态规划法求解0/1背包问题:\nX=[");

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

            cout<<X[i]<<" ";//输出所求X[n]矩阵

        printf("]   装入总价值%d\n",sum2);

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

        {

            a[i]=b[i];

        }//恢复a[N]顺序

    }

        3）复杂度分析:

动态规划法求解0/1背包问题的时间复杂度为：n*C

3.回溯法求解0/1背包问题：

1）基本思想：

回溯法：为了避免生成那些不可能产生最佳解的问题状态，要不断地利用限界函数(bounding function)来处死那些实际上不可能产生所需解的活结点，以减少问题的计算量。这种具有限界函数的深度优先生成法称为回溯法。

对于有n种可选物品的0/1背包问题，其解空间由长度为n的0-1向量组成,可用子集数表示。在搜索解空间树时，只要其左儿子结点是一个可行结点，搜索就进入左子树。当右子树中有可能包含最优解时就进入右子树搜索。

      2）代码:

       #include<iostream>

       #include<algorithm>

       usingnamespace std;

       #define N100    //最多可能物体数

       structgoods //物品结构体

       {

           int sign;    //物品序号

           int w;   //物品重量

           int p;   //物品价值

       }a[N];

       boolm(goods a,goods b)

       {

           return (a.p/a.w)>(b.p/b.w);

       }

       int max(inta,int b)

       {

           return a<b?b:a;

       }

       intn,C,bestP=0,cp=0,cw=0;

       intX[N],cx[N];

       int BackTrack(inti)

      {

           if(i>n-1){

               if(bestP<cp){

                    for (int k=0;k<n;k++)   X[k]=cx[k];//存储最优路径

                   bestP=cp;

               }

               return bestP;

           }

            if(cw+a[i].w<=C){   //进入左子树

               cw=cw+a[i].w;

               cp=cp+a[i].p;

               cx[a[i].sign]=1; //装入背包

               BackTrack(i+1);

               cw=cw-a[i].w;

               cp=cp-a[i].p;    //回溯，进入右子树

           }

           cx[a[i].sign]=0; //不装入背包

           BackTrack(i+1);

           return bestP;

       }

       intKnapSack3(int n,goods a[],int C,int x[])

       {

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

           {

               x[i]=0;

               a[i].sign=i;

           }

            sort(a,a+n,m);//将各物品按单位重量价值降序排列

           BackTrack(0);

           return bestP;

       }

       int main()

       {

           goods b[N];

           printf("物品种数n: ");

           scanf("%d",&n);  //输入物品种数

           printf("背包容量C: ");

           scanf("%d",&C);  //输入背包容量

           for (int i=0;i<n;i++)    //输入物品i的重量w及其价值v

           {

               printf("物品%d的重量w[%d]及其价值v[%d]:  ",i+1,i+1,i+1);

               scanf("%d%d",&a[i].w,&a[i].p);

               b[i]=a[i];

           }

       intsum3=KnapSack3(n,a,C,X);//调用回溯法求0/1背包问题

           printf("回溯法求解0/1背包问题:\nX=[");

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

            cout<<X[i]<<" ";//输出所求X[n]矩阵

            printf("]   装入总价值%d\n",sum3);

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

          {

               a[i]=b[i];

          }//恢复a[N]顺序

3）复杂度分析：

最不理想的情况下，回溯法求解0/1背包问题的时间复杂度为：2^n。由于其对蛮力法进行优化后的算法，其复杂度一般比蛮力法要小。

空间复杂度：有n个物品，即最多递归n层，存储物品信息就是一个一维数组，即回溯法求解0/1背包问题的空间复杂度为n。

回溯法的另一版本：

   #include <iostream>  
#include <cstdio>  
#include <algorithm>  
using namespace std;  
#define MAXN 10  
struct Goods_Info 
{ 
    int v;      //价值  
    int w;      //重量  
    double vw;  //价值重量比  
}goods[MAXN]; 
 
int n; 
int maxValue; 
bool solu[MAXN]; 
bool optimalSolu[MAXN]; 
 
bool Cmp(const Goods_Info a, const Goods_Info b) 
{ 
    return a.vw > b.vw; 
} 
//可装入一部分物品时，取得的最优价值  
double Bound(int i, double v, int c) 
{ 
    //以物品的价值重量比递减将物品装入背包  
    while (i <= n && goods[i].w <= c) 
    { 
        v += goods[i].v; 
        c -= goods[i].w; 
        i++; 
    } 
    //将背包装满  
    if (i <= n) 
    { 
        v += (goods[i].vw * c); 
    } 
    return v; 
} 
void Backtrack(int k, int cv, int rc) 
{ 
    if (k > n) 
    { 
        if (cv > maxValue) 
        { 
            maxValue = cv; 
            int i; 
            for (i = 1; i <= n; i++) 
            { 
                optimalSolu[i] = solu[i]; 
            } 
        } 
    } 
    else 
    { 
        if (goods[k].w <= rc) //当前物品能否装入背包  
        { 
            solu[k] = true; 
            Backtrack(k+1, cv+goods[k].v, rc-goods[k].w); 
        } 
        if (Bound(k+1, cv, rc) > maxValue) //剩余物品的最优价值是否更优  
        { 
            solu[k] = false; 
            Backtrack(k+1, cv, rc); 
        } 
    } 
}  
int main(void) 
{ 
    int c; 
    while (scanf("%d%d", &n, &c) != EOF) 
    { 
        int i; 
        for (i = 1; i <= n; i++) 
        { 
            scanf("%d%d", &goods[i].v, &goods[i].w); 
            goods[i].vw = (double)goods[i].v / goods[i].w; 
        } 
 
        //将物品按照价值重量比递减排序  
        sort(goods+1, goods+n+1, Cmp); 
 
        maxValue = 0; 
        Backtrack(1, 0, c); 
 
        printf("%d\n", maxValue); //最优值  
         
        /*
        //最优解
        printf("value:");
        for (i = 1; i <= n; i++)
        {
            printf("\t%d", goods[i].v);
        }
        printf("\nweight:");
        for (i = 1; i <= n; i++)
        {
            printf("\t%d", goods[i].w);
        }
        printf("\nstatus:");
        for (i = 1; i <= n; i++)
        {
            printf("\t%d", optimalSolu[i]);
        }
        printf("\n");
        */ 
    } 
    return 0; 
} 

4.分支限界法求解背包问题：

1）基本思想：

分支限界法类似于回溯法，也是在问题的解空间上搜索问题解的算法。一般情况下，分支限界法与回溯法的求解目标不同。回溯法的求解目标是找出解空间中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。

首先，要对输入数据进行预处理，将各物品依其单位重量价值从大到小进行排列。

在下面描述的优先队列分支限界法中，节点的优先级由已装袋的物品价值加上剩下的最大单位重量价值的物品装满剩余容量的价值和。

算法首先检查当前扩展结点的左儿子结点的可行性。如果该左儿子结点是可行结点，则将它加入到子集树和活结点优先队列中。当前扩展结点的右儿子结点一定是可行结点，仅当右儿子结点满足上界约束时才将它加入子集树和活结点优先队列。当扩展到叶节点时为问题的最优值。

2）代码:

#include<iostream>

#include<algorithm>

using namespace std;

#define N 100 //最多可能物体数

struct goods  //物品结构体

{

    int sign;  //物品序号

    int w; //物品重量

    int p; //物品价值

}a[N];

bool m(goods a,goods b)

{

    return (a.p/a.w)>(b.p/b.w);

}

int max(int a,int b)

{

    return a<b?b:a;

}

int n,C,bestP=0,cp=0,cw=0;

int X[N],cx[N];

struct KNAPNODE   //状态结构体

{

    bool s1[N]; //当前放入物体

    int k;     //搜索深度

    int b; //价值上界

    int w; //物体重量

    int p; //物体价值

};

struct HEAP   //堆元素结构体

{

    KNAPNODE *p;//结点数据

    int b;        //所指结点的上界

};

//交换两个堆元素

void swap(HEAP &a, HEAP&b)

{

    HEAP temp = a;

    a = b;

    b = temp;

}

//堆中元素上移

void mov_up(HEAP H[], int i)

{

    bool done = false;

    if(i!=1){

       while(!done && i!=1){

           if(H[i].b>H[i/2].b){

              swap(H[i], H[i/2]);

           }else{

              done = true;

           }

           i = i/2;

       }

    }

}

//堆中元素下移

void mov_down(HEAP H[], intn, int i)

{

    bool done = false;

    if((2*i)<=n){

       while(!done && ((i = 2*i) <= n)){

           if(i+1<=n && H[i+1].b > H[i].b){

              i++;

           }

           if(H[i/2].b<H[i].b){

              swap(H[i/2], H[i]);

           }else{

              done = true;

           }

       }

    }

}

//往堆中插入结点

void insert(HEAP H[], HEAPx, int &n)

{

    n++;

    H[n] = x;

    mov_up(H,n);

}

//删除堆中结点

void del(HEAP H[], int&n, int i)

{

    HEAP x, y;

    x = H[i]; y = H[n];

    n --;

    if(i<=n){

       H[i] = y;

       if(y.b>=x.b){

           mov_up(H,i);

       }else{

           mov_down(H, n, i);

       }

    }

}

//获得堆顶元素并删除

HEAP del_top(HEAP H[], int&n)

{

    HEAP x = H[1];

    del(H, n, 1);

    return x;

}

//计算分支节点的上界

void bound( KNAPNODE* node,int M, goods a[], int n)

{

    int i = node->k;

    float w = node->w;

    float p = node->p;

    if(node->w>M){   //  物体重量超过背包载重量

       node->b = 0;   //  上界置为0

    }else{

       while((w+a[i].w<=M)&&(i<n)){  

           w += a[i].w;   // 计算背包已装入载重

           p += a[i++].p; //    计算背包已装入价值

       }

       if(i<n){

           node->b = p + (M - w)*a[i].p/a[i].w;

       }else{

           node -> b = p;

       }

    }

}

//用分支限界法实现0/1背包问题

int KnapSack4(int n,goodsa[],int C, int X[])

{

    int i, k = 0;      // 堆中元素个数的计数器初始化为0

    int v;

    KNAPNODE *xnode, *ynode, *znode;

    HEAP x, y, z, *heap;

    heap = new HEAP[n*n];        // 分配堆的存储空间

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

       a[i].sign=i;        //记录物体的初始编号

    }

    sort(a,a+n,m);             // 对物体按照价值重量比排序

    xnode = new KNAPNODE;        // 建立父亲结点

    for( i=0; i<n; i++){           //  初始化结点

       xnode->s1[i] = false;

    }

    xnode->k = xnode->w = xnode->p = 0;

    while(xnode->k<n) {

       ynode = new KNAPNODE;     // 建立结点y

       *ynode = *xnode;         //结点x的数据复制到结点y

       ynode->s1[ynode->k] = true;     //  装入第k个物体

       ynode->w += a[ynode->k].w;     //  背包中物体重量累计

       ynode->p += a[ynode->k].p;     //  背包中物体价值累计

       ynode->k ++;               //  搜索深度++

       bound(ynode, C, a, n); //       计算结点y的上界

       y.b = ynode->b;

       y.p = ynode;

        insert(heap, y, k);        //结点y按上界的值插入堆中

       znode = new KNAPNODE;     // 建立结点z

       *znode = *xnode;          //结点x的数据复制到结点z

       znode->k++;                         //   搜索深度++

       bound(znode, C, a, n); //计算节点z的上界

       z.b = znode->b;

       z.p = znode;

       insert(heap, z, k);     //结点z按上界的值插入堆中

       delete xnode;

       x = del_top(heap, k);   //获得堆顶元素作为新的父亲结点

       xnode = x.p;

    }

    v = xnode->p;

    for( i=0; i<n; i++){     //取装入背包中物体在排序前的序号

       if(xnode->s1[i]){

           X[a[i].sign] =1 ;

       }else{

           X[a[i].sign] = 0;

       }

    }

    delete xnode;

    delete heap;

    return v;              //返回背包中物体的价值

}

/*测试以上算法的主函数*/

int main()

{

    goods b[N];

    printf("物品种数n: ");

    scanf("%d",&n);   //输入物品种数

    printf("背包容量C: ");

    scanf("%d",&C);   //输入背包容量

    for (int i=0;i<n;i++)    //输入物品i的重量w及其价值v

    {

       printf("物品%d的重量w[%d]及其价值v[%d]:  ",i+1,i+1,i+1);

       scanf("%d%d",&a[i].w,&a[i].p);

       b[i]=a[i];

    }

intsum4=KnapSack4(n,a,C,X);//调用分支限界法求0/1背包问题

    printf("分支限界法求解0/1背包问题:\nX=[ ");

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

       cout<<X[i]<<" ";//输出所求X[n]矩阵

    printf("]  装入总价值%d\n",sum4);

    return 0;

}

3)复杂度分析：

          分支限界法求解0/1背包问题的时间复杂度为：2^n。

      相同的数据，求相同同的问题，用不同的方法，得到的结果，所得结果                     

      正式所求问题的最优解，所编程序是正确的。

 ————————————————————————————————————————————————————————————

简单背包问题：递归/非递归

链接：http://blog.csdn.net/zhaom_916/article/details/7426629

1. /** 
2. 简单背包问题 
3. 问题定义： 
4. 有一个背包重量是S，有n件物品，重量分别是W0,W1...Wn-1 
5. 问能否从这n件物品中选择若干件放入背包中使其重量之和正好为S 
6. */  
7. #include <iostream>  
8. #include <algorithm>  
9. #include <vector>  
10. #include <string>  
11. using namespace std;  
12. const int maxsize=100;  
13. int n,S;//n是有多少中物品，S是要凑足的重量  
14. bool visit[maxsize];//标记是否被访问过，别访问过标记为1，没有访问过为0  
15. int w[maxsize];//记录每一种物品的重量  
16. int q[maxsize];//相当于一个栈，存储被访问过的物品的编号  
17. int beibao()  
18. {  
19.     int top=-1,begin=0,sum=0;  
20.     int i;  
21.     while(top!=-2)  
22.     {  
23.         //从第一个物品开始循环  
24.         for(i=begin;i<n;i++)  
25.         {  
26.             //如果没有被访问过，并且加上重量之和小于S  
27.             if(!visit[i] && w[i]+sum<=S)  
28.             {  
29.                 sum+=w[i];//在sum上加上当前物品的重量  
30.                 q[++top]=i;//把物品的编号存入q[]中  
31.                 begin=0;//从头开始访问  
32.                 visit[i]=1;//该结点访问过标记  
33.                 if(sum==S) return top;//如果成功，返回top，top为数组元素的个数，有所有物品的编号  
34.                 break;  
35.             }  
36.         }  
37.         //如果检索到最后，也就是说栈顶前面的物品都不符合条件  
38.         //因此可能栈内的元素有问题，所以弹出栈顶元素，不把栈顶元素计算在内  
39.         if(i==n)  
40.         {  
41.             visit[q[top]]=0;//把栈顶元素定义成未访问  
42.             sum-=w[q[top]];//从和中减去站定物品编号的重量  
43.             begin=q[top]+1;//从栈顶元素的下一个物品开始检索  
44.             //cout<<"------"<<begin<<endl;  
45.             top--;//栈递减一个单位  
46.         }  
47.     }  
48. }  
49. //背包问题递归版本  
50. /** 
51. 解释：其选择只有两种可能，选择一组物品中包含Wn-1 ，此时knap(s,n)的解就是knap(s - Wn-1,n-1)的解 
52. 如果选择的物品中不包括Wn-1，这样knap(s,n)的解就是knap(s,n-1)的解 
53. knap(s,n) = true, 当 s=0时 
54.             false ，当s < 0 或者 s > 0 且 n < 1 
55.             knap(s - Wn-1,n-1) || knap(s,n-1) 当s>0且n>=1 
56. */  
57. bool knap(int s,int n)  
58. {  
59.     if(s == 0) return true;//递归出口 在s恰好为0时 递归结束  
60.     if(s < 0 || (s > 0&&n < 0)) return false;//或者s小于0 n 小于0时  
61.     if(knap(s - w[n - 1],n - 1))  
62.     {  
63.         cout<<w[n - 1];  
64.         return true;  
65.     }else return knap(s,n - 1);  
66. }  
67. int main()  
68. {  
69.     cin>>n>>S;  
70.     for(int i=0;i<n;i++)  
71.     {  
72.         cin>>w[i];  
73.         visit[i]=0;  
74.     }  
75.     int t=beibao();  
76.     knap(S,n);  
77.     if(t!=-1)  
78.     {  
79.         for(int i=0;i<=t;i++)  
80.             cout<<w[q[i]]<<" ";  
81.         cout<<endl;  
82.     }  
83.     else cout<<-1<<endl;  
84. }