学步园

问题描述

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