0-1背包问题的递归回溯算法实现(C++)-创新互联

编译环境:Dev-C++

10年积累的成都网站制作、网站建设、外贸网站建设经验,可以快速应对客户对网站的新想法和需求。提供各种问题对应的解决方案。让选择我们的客户得到更好、更有力的网络服务。我虽然不认识你,你也不认识我。但先做网站设计后付款的网站建设流程,更有宜宾免费网站建设让你可以放心的选择与我们合作。

递归回溯方法求解0-1背包问题的具体算法实现


0-1背包问题描述:

我们有n种物品,物品j的重量为wj,价格为pj。我们假定所有物品的重量和价格都是非负的。背包所能承受的大重量为c。如果限定每种物品只能选择0个或1个,则问题称为0-1背包问题。计算出背包能承受的大价值量。

0-1背包问题形式化描述:

给定c>0,wi>0,vi>0,1≤i≤n,求n元0-1向量(x1, x2, …, xn),使得

在本次试验中,使用到的实例为:n=7,c=150,w={35,30,60,50,40,10,25},p={10,40,30,50,35,40,30}.  


算法设计实现描述:

回溯法在包含问题的所有解的解空间树中按照深度优先的策略,确定了解空间的组织结构后,回溯法从开始节点出发,以深度优先方式搜索整个解空间,这个开始节点成为活节点,同时成为当前的扩展结点。

在当前的可扩展结点处,搜索向纵深方向移至一个新的结点,这个新结点成为当前的活结点,并成为扩展结点。如果在当前的可扩展结点处不能向纵深方向移动(结点不包含问题解,或者到达叶子结点),则当前扩展结点变成死结点。此时,应回溯至最近的一个活动结点处,并使这个活动结点成为当前的扩展结点。回溯法以这种工作方式递归地在解空间中搜索,直至找到所要求的解或者解空间中已无活动结点为止。

不妨设  bestw :当前最优载重量;

cw   :当前扩展结点Z的载重量 ;

 r    :当前扩展结点Z的剩余集装箱重量;

回溯法解题步骤:

1、针对所给问题,定义问题的解空间;

2、确定易于搜索的解空间结构;

3、以深度优先搜索的方式搜索解空间,并且在搜索过程中用剪枝函数避免无效搜索

剪枝函数:

1、搜索左子树时:用约束函数在扩展结点处剪去不满足约束的左子树(约束函数cw+wi >C时,剪掉左子树)

2、搜索右子树时:用限界函数剪去得不到最优解的右子树(限(上)界函数cp+r

递归回溯流程图:


调试过程及结果

程序执行的结果:

0-1背包问题回溯算法的复杂性分析:

在本算法中,计算上界需要O(n)时间,在最坏情况下有O(2­n) 个右儿子结点需要计算上界。所以,解0-1背包问题的回溯算法Backtrack所需要的计算时间为O(n2­n)。


源代码:
#includeusing namespace std;
class Knap{
    friend int Knapsack(int*,int*,int,int,Knap&);
public:
    int c;      //背包容量
    int n;      //物品个数
    int* w;     //重量信息
    int* p;     //价值信息
    int cw;     //当前重量
    int cp;     //当前价值
    int bestp;  //当前最优价值
    int *x,     //当前解
        *bestx; //当前最优解
    int Bound(int i);            //限界函数
    void Backtrack(int i);       //递归深度优先遍历
};
int Knap::Bound(int i){
    int cleft = c - cw;
    int b = cp;
    while(i<=n&&w[i]<=cleft){
        b += p[i];
        cleft -= w[i];
        i++;
    }
    if(i<=n) b += cleft*(p[i]/w[i]);
    return b;
}
void Knap::Backtrack(int i){
    if(i>n){
        bestp = cp;
        for(int i=1;i<=n;i++){
            bestx[i] = x[i];
        }
        for(int i=1;i<=n;i++){
            cout<bestp)//Bound(i+1)代表第i层右子树的限界函数
        {
            x[i] = 0;
            Backtrack(i+1);  //继续深度优先搜索
        }

    }
}
class Object{               //物品类
    friend int Knapsack(int*,int*,int,int,Knap&);
    friend bool cmp(Object,Object);
private:
    int id;
    double aver;
};
bool cmp(Object a,Object b){
    return a.aver>b.aver;
}
int Knapsack(int* w,int* p,int c,int n,Knap& K){
    int W = 0;
    int P = 0;
    Object* Q = new Object[n];
    for(int i=1;i<=n;i++){
        Q[i-1].id = i;
        Q[i-1].aver = 1.0*p[i]/w[i];
        P += p[i];
        W += w[i];
}
    if(W>n>>c;
    w = new int[n+1];
    p = new int[n+1];
    cout<<"input weight of objects"<>w[i];
    }
    cout<<"input value of objects"<>p[i];
    }
}
void Print(int bestp,int n,int*& x){
    cout<<"max value is"<

你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧


本文题目:0-1背包问题的递归回溯算法实现(C++)-创新互联
浏览地址:http://scyanting.com/article/dgseip.html