0-1背包-回溯法

偏执的太偏执、 2021-09-30 00:58 265阅读 0赞

**算法描述：**

0-1背包的回溯法，与装载问题的回溯法十分相似。在搜索解空间树时，只要其左儿子结点是一个可行结点，搜索就进入其左子树。当右子树中有可能包含最优解时才进入右子树进行搜索。否则将右子树剪去。

计算右子树上界的更好算法是：

将剩余物品依其单位重量价值排序，然后依次装入物品，直至装不下时，再装入该物品的一部分而装满背包。

**算法实现：**

由Bound函数计算当前节点处的上界。

类Knap的数据成员记录解空间树的节点信息，以减少参数传递及递归调用所需的栈空间。

在解空间树的当前扩展结点处，仅当要进入右子树时，才计算上界bound，以判断是否可将右子树剪去。

进入左子树时不需要计算上界，因为它与其父节点的上界相同。

**算法实现：**（代码有点小问题，正在修改中）

![复制代码][copycode.gif]

#include <iostream>
    #include <stdio.h>
    #include <stdlib.h>
    using namespace std;
    template <class Typew,class Typep>
    class Knap{
            friend Typep Knapsack(Typep *,Typew *,Typew,int);
            private:
                    Typep Bound(int i);
                    void Backtrack(int i);
                    Typew c;//背包容量
                    int n;//物品数
                    Typew * w;//物品重量数组
                    Typep * p;//物品价值数组
                    Typew cw;//当前重量
                    Typep cp;//当前价值
                    Typep bestp;//当前最优价值
    };
    template <class Typew,class Typep>
    void Knap<Typew,Typep>::Backtrack(int i)
    {
            if(i>n)//到达叶子
            {
                    bestp = cp;
                    return;
            }
            if(cw+w[i] <= c)//进入左子树
            {
                    cw += w[i];
                    cp += p[i];
                    Backtrack(i+1);
                    cw -= w[i];
                    cp -= p[i];
            }
            if(Bound(i+1)>bestp)//进入右子树
                    Backtrack(i+1);
    }
    template <class Typew,class Typep>
    Typep Knap<Typew,Typep>::Bound(int i)//计算上界
    {
            Typew cleft = c- cw;//剩余容量
            Typep b = cp;
            while(i<=n && w[i]<=cleft)//以物品单位重量价值递减序装入物品
            {
                    cleft -= w[i];
                    b += p[i];
                    i++;
            }
            //装满背包
            if(i<=n)
                    b+=p[i]*cleft/w[i];
    
            return b;
    }
    class Object
    {
            friend int Knapsack(int *,int *,int,int);
    public:
            int operator <= (Object a)const
            {
                    return (d >= a.d);
            }
    private:
            int ID;
            float d;
    };
    int compare (const void * a, const void * b) 
    { 
      return ( *(int*)a - *(int*)b );
    }
    template <class Typew,class Typep>
    Typep Knapsack(Typep p[],Typew w[],Typew c,int n)
    {
            int i;
            //初始化
            int W = 0;
            int P = 0;
            Object* Q = new Object[n];
            for(i=0;i<n;i++)
            {
            //        cout<<p[i]<<" "<<w[i]<<endl<<"-------------------------"<<endl;
                    Q[i].ID = i;
                    Q[i].d = 1.0*p[i]/w[i];
            //        cout<<Q[i].ID<<" "<<Q[i].d<<endl<<"----------------------"<<endl;
                    P += p[i];
                    W += w[i];
            //        cout<<P<<" "<<W<<endl<<endl; 
            }
            if(W<=c)
                    return P;//装入所有物品
            //依物品单位重量价值排序
            qsort (Q,n, sizeof(int), compare);
            Knap<Typew,Typep> K;
            K.p = new Typep [n+1];
            K.w = new Typew [n+1];
            for(i =1;i<=n;i++)
            {
                    K.p[i] = p[Q[i-1].ID];
                    K.w[i] = w[Q[i-1].ID];
            }
            K.cp = 0;
            K.cw = 0;
            K.n = n;
            K.bestp = 0;
            K.Backtrack(1);
    //        cout<<K.bestp<<endl;
            delete [] Q;
            delete [] K.w;
            delete [] K.p;
    
            
            return K.bestp;
    }
    int main()
    {
    
            int p[4] = {9,10,7,4};
            int w[4]= {3,5,2,1};
            int num = Knapsack(p,w,7,4);
            cout<<num<<endl;
            return 0;
    }

![复制代码][copycode.gif]

转载于:https://www.cnblogs.com/luozhijun/p/6880527.html

[copycode.gif]: /images/20210725/840ed4b495204945a64c16c1bcce7568.png