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

编译环境：Dev-C++

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

我们有n种物品，物品j的重量为wj，价格为pj。我们假定所有物品的重量和价格都是非负的。背包所能承受的大重量为c。如果限定每种物品只能选择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

递归回溯流程图：

程序执行的结果:

在本算法中，计算上界需要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元起，快前往官网查看详情吧