背包问题之分枝界限

问题描述

    背包的容量为C，现有N件物品，价格分别为p[0],p[1]......p[n-1].重量分别为：w[0],w[1]......w[n-1].从N件物品中选择任意个放入背包中，使得物体的价值最大并且总重量不超过背包的容量C。

       采用数学语言描述如下：

      在  w[0]*x[0] + w[1] *x[1]+....... +w[n-1]*x[n-1]  < C, x[i] = 0 或1 的条件下

      求  p[0]*x[0] + p[1] *x[1]+....... +p[n-1]*x[n-1]   的最大值。

 

 分枝界限介绍

   分枝界限可以说是dfs和bfs的结合，综合了DFS算法空间复杂度低和BFS时间复杂度低的优点。分枝界限法在回溯法的基础上更进了一步，在回溯法中，一旦从问题状态空间树导出的解不满足约束函数，我们就将其分枝剪掉。在处理此类问题时，回溯法的思想可以进一步强化。在回溯法的基础上加上两个额外的条件就变成了分支界限法

           1.  对于一棵状态空间树的每一个结点所代表的部分解， 我们要提供一种算法，计算出通过这个部分解所繁衍也的任何解在目标函数

            上的最佳边界。

            2. 目前所求得的最佳解。

   有了这两个条件，我们可以用当前求得的最佳解和所有结点的最佳边界比较，如果某结点的最佳边界不能超越当前最佳解（在求最大化问题

中，该结点的最佳上界不大于当前最佳解，在求最小化问题中，该结点的最佳下界不小于当前最佳解），则将其剪掉。这就是分枝界限的主要相思。

 

 问题分析。

    在背包问题中，怎样求最佳边界呢，最简单的一种求法是将物品的按价值重量比（p[i]/w[i]）排序，将已经选择好的物品总价值currentValue加上背包剩余重量C-currentWeight(currentWeight为当前背包中物品的总重量）与剩下物品最价值重量比（p[i]/w[i])的积:

                                   ub = currentValue + (C-currentWeight)*(p[i]/w[i]);

 当然还有更优的求最佳上界的方法。

    下面，举一个最简单的例子来说明

背包的容量为10，有4个物品，重量分别为4,5,7,4。价值分别为40,42,28,20。按价值/重量排序如下

 

  物品              重量                   价值               价值/重量

    1                  4                        40                10

    2                  7                        42                6

    3                  5                        25                5

    4                  3                        12                4

 

用c,v,w,ub分别表示背包的容量，当前背包内物品的价值，当前背包内物品的总重量，结点的最佳上界，用二叉树来表示

 

 

代码如下：

 

#include <iostream>#include <vector>#include <algorithm>#include <functional>using namespace std;//背包问题，使用分枝界限求解，//保存背包内物品选择情况的结点类struct Node{ int value; int weight; int ub; //价格上界 vector<bool> solution; //物品选择，1表示选择，0表示未选择};bool myCmp1(const Node& left,const Node& right){ return left.ub > right.ub;}//物品struct Thing{ int weight; int value;};bool myCmp2(const Thing& left,const Thing& other){ return (left.value/left.weight) > (other.value/other.weight);}//背包类class Pack{protected: int m_c; //背包的容量 int m_num; //物品的件数 vector<Thing> m_thing;private: //计算最价值最佳上界 void CaculateUb(Node& node) { node.ub = node.value + (m_c-node.weight)*m_thing[node.solution.size()].value; }public: //构造函数 Pack(); Pack(vector<Thing>& t, int c,int n) :m_thing(t),m_c(c),m_num(n) { //按价值重量比排序 sort(m_thing.begin(),m_thing.end(),myCmp2); } //获取背包内物品的最大值 int GetBestValue() { vector<Node> state;//状态空间树 //初始化根结点 Node root; root.value=root.weight =0; root.solution.clear(); CaculateUb(root); state.push_back(root); //在此使用最大堆来实现，堆的顶总是保存ub最大的结点， //因此如果堆顶的结点已经全部分配完成，就表示已经找到最优解 while(state.front().solution.size() < m_num) { //取具有最大上界的结点扩展 pop_heap(state.begin(),state.end(),myCmp1); Node expand = state.back(); state.pop_back(); Node expLeft,expRight; //选择下一件物品 if(expand.weight+m_thing[expand.solution.size()].weight <=m_c) { expLeft.weight = expand.weight+m_thing[expand.solution.size()].weight; expLeft.value = expand.value + m_thing[expand.solution.size()].value; expLeft.solution = expand.solution; expLeft.solution.push_back(true); CaculateUb(expLeft); state.push_back(expLeft); } //不选择下一件物品 expRight.weight = expand.weight; expRight.value = expand.value; expRight.solution = expand.solution; expRight.solution.push_back(false); CaculateUb(expRight); state.push_back(expRight); //生成最大堆 make_heap(state.begin(),state.end(),myCmp1); } return state.front().ub; }};int main(void){ //测试程序 int n; int c; cout << "请输入物品的件数" << endl; cin >>n; cout << "请输入背包的容量" << endl; cin >>c; vector<Thing> w(n); cout << "请输入物品的重量:" << endl; for(int i=0;i<n;++i) cin >> w[i].weight; cout << "请输入物品的价格:" << endl; for(int j=0;j<n;++j) cin >> w[i].value; Pack pack(w,c,n); int bestValue = pack.GetBestValue(); cout << "背包内的物品的最大价值为：" << bestValue << endl; return 0;}