一、问题

n皇后问题的解空间树是一颗排列树，而01背包问题的解空间树应该是一颗子集树。再简述下该问题：有n件物品和一个容量为c的背包。第i件物品的价值是v[i]，重量是w[i]。求解将哪些物品装入背包可使价值总和最大。所谓01背包，表示每一个物品看成一个整体，要么全部装入，要么都不装入。这里n=5, c=10, w={2, 2, 6, 5, 4}, v={6, 3, 5, 4, 6}。

01背包属于找最优解问题，用回溯法需要构造解的子集树。在搜索状态空间树时，只要左子结点是可一个可行结点，搜索就进入其左子树。对于右子树时，先计算上界函数，以判断是否将其剪枝。为了更好地计算和运用上界函数剪枝，可以先将物品按照其单位重量价值从大到小排序，此后就按照顺序考虑各个物品。

剪枝的两种情况：

①左结点深度搜索的条件是当前物品装得下，即cw+w[i]<=c

②将当前剩余所有物品都装入背包，获得的总价值也没能大于当前已经求得的最大价值bestp时

二、c++代码

#include <iostream>#include <cmath>using namespace std;int n;//物品数量double c;//背包容量double v[100];//各个物品的价值double w[100];//各个物品的重量double cw = 0.0;//当前背包重量double cp = 0.0;//当前背包中物品价值double bestp = 0.0;//当前最优价值double perp[100];//物品按单位重量价值排序后int x[100];//是否装入，为0或1 int best[100];//记录最优解，为0或1 double v2[100];//临时存放各个物品的价值double w2[100];//临时存放各个物品的重量//交换两元素 void swap(int i,int j,double arr[]){     double t;     t=arr[i];arr[i]=arr[j];arr[j]=t;                     } //快速排序算法 void quicksort(int p,int q,double arr[],double key){    int i,j;    i=p;    j=q;    if(p>=q){         return;         }        while(1){            while(j>=p && arr[j]<key){j--;}            if(j<=i)             break;            swap(i,j,arr);            swap(i,j,w2);            swap(i,j,v2);                        while(i<=q && arr[i]>=key){i++;}                                              if(j<=i)             break;            swap(i,j,arr);            swap(i,j,w2);            swap(i,j,v2);                                  }                 quicksort(p,j-1,arr,arr[p]);     quicksort(j+1,q,arr,arr[j+1]);           }//按单位价值排序void knapsack(int t){          quicksort(t,n,perp,perp[t]);    }//回溯函数//每个结点的左右子树都要判断，因为装或不装两种情况都要考虑 void backtrack(int i){    double bound(int i);       if(i>n)//到达叶结点，得出一个解     {    bestp = cp;    for(int k=1;k<=n;k++)    {             best[k]=x[k];//把最优解记录下来          }       return;    }        if(cw+w[i]<=c)//搜索左子树     {       cw+=w[i];       cp+=v[i];       x[i]=1;       backtrack(i+1);       cw-=w[i];       cp-=v[i];       x[i]=0;    }          if(bound(i+1)>bestp)//搜索右子树，必要时剪枝        backtrack(i+1);}//计算上界函数double bound(int i){    double leftw= c-cw;    double b =cp;        for(int k=i;k<=n;k++){//剩余物品重量、价值分别存在w2、v2数组中              w2[k]=w[k];             v2[k]=v[k];             }     knapsack(i);//将剩余物品按单位重量价值排序        while(i<=n&&w2[i]<=leftw)//将剩余已排好序的物品装入背包     {       leftw-=w2[i];       b+=v2[i];       i++;    }    if(i<=n)       b+=v2[i]/w2[i]*leftw;    return b;}int main(){    int i;     cin >> n >> c;//输入物品数量n、背包容量c       for(i=1;i<=n;i++)    {       cin >> w[i] >> v[i];//输入各个物品重量wi、价值vi         perp[i]=v[i]/w[i];         w2[i]=v2[i]=0;              x[i]=0;       best[i]=0;    }            backtrack(1);    cout << "最大价值为：" << bestp << endl;    cout << "需要装入的物品编号是：" << endl;    for(i=1;i<=n;i++)    {       if(best[i])           cout << i << " ";    }    cout << endl;    system("pause");     return 0;}

运行结果：