01背包问题 -- 回溯法 2

/*0-1背包伪代码*/
#include    
using namespace std;        
template    
class Knap    //Knap类记录解空间树的结点信息 
{        template        friend Typep Knapsack(Typep [],Typew [],Typew,int);  //负责对变量初始化，调用递归函数 Backtrack(1)实现回溯搜索并返回最大装包价值private:            Typep Bound(int i);  //计算以当前结点为根的子树的价值上界        void Backtrack(int i);  //核心函数，对解空间树回溯搜索，求得最大装包价值Typew c;    //背包容量           int n;      //装包物品数量            Typew *w;     //物品重量数组          Typep *p;     //物品价值数组           Typew cw;     //当前重量，从根到当前结点所形成的部分解的装包物品重量      Typep cp;       //当前价值，从根到当前结点所形成的部分解的装包物品价值Typep bestp;    //当前最优价值，已搜索过的部分解空间树的最优装包价值  
};     template    
Typep Knapsack(Typep p[],Typew w[],Typew c,int n);  //声明背包问题求解函数     
template     
inline void Swap(Type &a,Type &b);  //声明交换函数     
template    
void BubbleSort(Type a[],int n);  //声明冒泡排序函数   int main()   
{        int n; //物品数       int c; //背包容量        cout<<"物品个数为："; cin>>n;  cout<<"背包容量为：";  cin>>c;    int *p = new int[n];//物品价值 下标从1开始      int *w = new int[n];//物品重量 下标从1开始        cout<<"物品重量分别为："<>w[i];       }   cout<<"物品价值分别为："<>p[i];       }      cout<<"物品重量和价值分别为："<    
void Knap::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    
Typep Knap::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 += cleft /w[i]*p[i];  //则将物品的部分装入到背包中    }      return b;   
}       class Object  //定义对象类，作用相当于结构体 
{        template        friend Typep Knapsack(Typep[],Typew [],Typew,int);    public:            int operator >= (Object a)const  //符号重载函数，重载>=符号        {                return (d>=a.d);           }       private:            int ID;   //编号          float d;   //单位重量的价值    
};template    
Typep Knapsack(Typep p[],Typew w[],Typew c,int n)   
{        //为Knap::Backtrack初始化       Typew W = 0;       Typep P = 0;        Object *Q = new Object[n];//创建Object类的对象数组|   //初始化Object类的对象数组|     for(int i=1; i<=n; i++)       {            Q[i-1].ID = i;            Q[i-1].d = 1.0 * p[i]/w[i];           P += p[i];           W += w[i];       }        if(W <= c)//装入所有物品      {            return P;       }        //依物品单位重量价值降序排序       BubbleSort(Q,n);        Knap K;  //创建Knap的对象K     K.p = new Typep[n+1];K.w = new Typew[n+1];      for(int i=1; i<=n; i++)       {            K.p[i] = p[Q[i-1].ID];           K.w[i] = w[Q[i-1].ID];      }     //初始化K     K.cp = 0;       K.cw = 0;       K.c = c;       K.n = n;       K.bestp = 0;            //对解空间树回溯搜索，求得最大装包价值  K.Backtrack(1);       delete []Q;       delete []K.w;      delete []K.p;        return K.bestp;  //返回最大装包价值
}       template    
void BubbleSort(Type a[],int n)   
{         //记录一次遍历中是否有元素的交换         bool exchange;           for(int i=0; i=a[j-1])                 {                      Swap(a[j],a[j-1]);                    exchange = true;                 }              }               //如果这次遍历没有元素的交换，那么排序结束              if(exchange==false)             {                 break              }        }
}       
template     
inline void Swap(Type &a,Type &b)  //交换函数 
{        Type temp = a;       a = b;       b = temp;   
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！