算法描述：

0-1背包的回溯法，与装载问题的回溯法十分相似。在搜索解空间树时，只要其左儿子结点是一个可行结点，搜索就进入其左子树。当右子树中有可能包含最优解时才进入右子树进行搜索。否则将右子树剪去。

　　计算右子树上界的更好算法是：

　　　　将剩余物品依其单位重量价值排序，然后依次装入物品，直至装不下时，再装入该物品的一部分而装满背包。

算法实现：

　　由Bound函数计算当前节点处的上界。

　　类Knap的数据成员记录解空间树的节点信息，以减少参数传递及递归调用所需的栈空间。

　　在解空间树的当前扩展结点处，仅当要进入右子树时，才计算上界bound，以判断是否可将右子树剪去。

　　进入左子树时不需要计算上界，因为它与其父节点的上界相同。

算法实现：（代码有点小问题，正在修改中）

#include 
     
      #include 
      
       #include 
       
        using namespace std;template 
        
         class Knap{        friend Typep Knapsack(Typep *,Typew *,Typew,int);        private:                Typep Bound(int i);                void Backtrack(int i);                Typew c;//背包容量                int n;//物品数                Typew * w;//物品重量数组                Typep * p;//物品价值数组                Typew cw;//当前重量                Typep cp;//当前价值                Typep bestp;//当前最优价值};template 
         
          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+=p[i]*cleft/w[i]; return b;}class Object{ friend int Knapsack(int *,int *,int,int);public: int operator <= (Object a)const { return (d >= a.d); }private: int ID; float d;};int compare (const void * a, const void * b) { return ( *(int*)a - *(int*)b );}template 
             
              Typep Knapsack(Typep p[],Typew w[],Typew c,int n){ int i; //初始化 int W = 0; int P = 0; Object* Q = new Object[n]; for(i=0;i
              
                K; K.p = new Typep [n+1]; K.w = new Typew [n+1]; for(i =1;i<=n;i++) { K.p[i] = p[Q[i-1].ID]; K.w[i] = w[Q[i-1].ID]; } K.cp = 0; K.cw = 0; K.n = n; K.bestp = 0; K.Backtrack(1);// cout<
               
                <