学步园

    最近复习了一下算法，觉得背包问题最具代表性。可以用大多数通用的算法（穷举，动规，回溯，分枝限界）来解决。因此将最近的笔记整理一下，发到自己的博客上。

      问题描述：背包的容量为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]   的最大值。

穷举算法的基本思想如下：

      枚举也所有可能的情况，找出其中的最大值。

用N位二进制数来表示N件物品的选取情况，例如在N＝3的情况下 ‘000’代表未选取任何物品，而 ‘101’代表选取了第1件和第3件物品。因此将 0 ---- 2^n-1 的情况枚举，找也最大值即可。

算法如下：

#include <iostream><br /> #include <vector></p> <p>using namespace std;</p> <p>class PackEnum<br /> {</p> <p> protected:<br /> vector<int> m_p; //N个背包的价格<br /> vector<int> m_w; //N个背包的重量<br /> int m_c; //背包的容量<br /> int m_num; //物品的件数</p> <p>public:<br /> //构造函数<br /> PackEnum();<br /> PackEnum(vector<int>& p,vector<int>& w, int c,int n)<br /> :m_p(p),m_w(w),m_c(c),m_num(n)<br /> {}</p> <p> //获取背包内物品的最大值<br /> int GetBestValue() const<br /> {<br /> int bestValue=0; //背包最大价值<br /> int currentValue =0; //当前背包中物品的价值<br /> int currentWeight =0; //当前背包中物品的重量</p> <p> const unsigned int max = 2 << m_num; //2的N次方</p> <p> //枚举所有可能的解<br /> for(unsigned int i =0; i<max;++i)<br /> {</p> <p> //清空背包<br /> currentValue =0;<br /> currentWeight =0;</p> <p> //取2进制数的每一位<br /> unsigned int bit = i;<br /> int j =0;<br /> while(bit !=0)<br /> {<br /> currentWeight += m_w[j] * (bit & 1);<br /> currentValue += m_p[j] * (bit & 1);<br /> //如果bit的最低位为1,则bit&1 = 1 ,否则为0</p> <p> bit >>=1;<br /> ++j;<br /> }</p> <p> //保存最优解<br /> if(currentWeight <=m_c<br /> && bestValue < currentValue)<br /> {<br /> bestValue = currentValue;<br /> }</p> <p> }<br /> return bestValue;<br /> }</p> <p>};</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<int> w(n);<br /> vector<int> p(n);</p> <p> cout << "请输入物品的重量:" << endl;<br /> for(int i=0;i<n;++i)<br /> cin >> w[i];<br /> cout << "请输入物品的价格:" << endl;<br /> for(int j=0;j<n;++j)<br /> cin >> p[j];</p> <p> PackEnum pack(p,w,c,n);</p> <p> int bestValue = pack.GetBestValue();</p> <p> cout << "背包内的物品的最大价值为：" << bestValue << endl;</p> <p> return 0;<br /> }</p> <p>

分析：

些算法的时间复杂度为 2^n, 并且要求（n<=32），所以算法的效率不高。但枚举算法是一种比较通用的算法，通常在找不到最佳的算法时，采用些算法。