回溯法之01背包问题

一、问题

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;
}
           

运行结果：