当前位置:编程学习 > C/C++ >>

回溯算法---01背包问题


背包问题:
         给定n种物品(每种物品仅有一件)和一个背包。物品i的重量是wi ,其价值为pi ,背包的容量为w。问应如何选择物品装入背包,使得装入背包中的物品的总价值最大?
            l  如果在装入背包时,物品可以切割,即可以只装入一部分,这种情况下的问题称为背包问题。
            l  在装入背包时,每种物品i只有两种选择,装入或者不装入,既不能装入多次,也不能只装入一部分。因此,此问题称为0-1背包问题。
        要想得到最优解,就要在效益增长和背包容量消耗两者之间寻找平衡。也就是说,总应该把那些单位效益最高的物体先放入背包。

背包问题可看做是一种回溯:
          每个包是一个节点, 节点共有2个候选值0、1 。 0代表不放人背包中, 1代表放入背包中。

 


      因此,背包问题就转换为找到满足条件的路径问题。

因此,可用回溯方法解决。


回溯方法解决背包问题:

方法一:

// 判断节点(I,j)是否为解路径上的节点,其中:
// 
//   i表示解路径上的第i个测试节点、j表示该节点的某个候选值
//   A[i] 保存第i个节点选用的值
 
BOOL TestNode(I ,j)
{
   更新相关参数值(假定选择了此候选值j,因此更新受影响的参数值);
 
   与0—(i-1) 层进行判断,看是否与以遍历的节点有冲突
 
   若有冲突, 则返回FALSE;
   若无冲突, 则 将节点i的值j,保存到对应的数组中A[I]=J;
 
   判断I是否为最后一层,
  若是最后一层,则成功找到一条解路径,返回TRUE;
 
  若不是最后一层,则判断第i+1层是否有正确的节点。
 
   BOOL bFlag=FALSE;
   FOR(k=0;k< CANDIDATA_NUM;k++) //候选值【0,。。。,CANDIDATA_NUM -1】
   {
        If(TestNode(i+1,k))
        {
           找到一个解;
           bFlag=True;
        }
        //不管TestNode(i+1,k)是成功的还是失败的,退出后,都要对参数进行还原
       还原相关参数值(撤销了候选值k,因此要还原受影响的参数值);
 
   }
 
   RETURN bFlag;
 
}
 
[cpp] 
int m,n=5,x[10]={0}; 
int w[6]={0,2,2,6,5,5},v[6]={0,6,3,5,4,6}; 
int c=10; 
int cw=0,cv=0,bestv=0; 
 
BOOL TestNode(int i,int j){  // 第 i个物品的 候选值为0和1 
 
 
    //更新相关参数值 
    cw+=w[i]*j; 
    cv+=v[i]*j; 
 
    //与之前的物品相比  有无冲突 
    if (cw>c) 
        return FALSE; 
 
    //无冲突,添加至解路径 
    x[i]=j; 
 
    // 到此为止  0--i行 均无冲突 
    // 如果是最后一行  成功找到一个解 
    if(i==n){ 
 
        for(i=1;i<=n;i++) 
            printf("%d",x[i]); 
        if(cv>bestv) 
            bestv=cv; 
        printf("\n"); 
        return TRUE; 
 
    } 
 
    //如果不是最后一行 则判断i+1行 
 
    BOOL bSuit=FALSE; 
    for (int k=0;k<=1;k++) 
    {        
        //第i+1行存在合适位置  
        if (TestNode(i+1,k)) 
            bSuit=TRUE;  
 
        //还原相关参数 
        cw-=w[i+1]*k; 
        cv-=v[i+1]*k; 
    } 
 
   return bSuit; 
 

 
 
 
void  Bag() 

 
    for (int i=0;i<=1;i++) 
    { 
        TestNode(1,i); 
    } 
 
 
 

或 不更新与还原相关变量, 而是根据已知信息推导相关变量值

[cpp] 
int m,n=5,x[10]={0}; 
int w[6]={0,2,2,6,5,5},v[6]={0,6,3,5,4,6}; 
int c=10; 
int cw=0,cv=0,bestv=0; 
 
BOOL TestNode(int i,int j){  // 第 i个物品的 候选值为0和1 
 
 
 
   //根据已知 推倒相关参数值 
    cw=0; 
    cv=0; 
    for (int k=1;k<=i-1;k++) 
    { 
        cw+=x[k]*w[k]; 
        cv+=x[k]*v[k]; 
    } 
 
    cw+=w[i]*j; 
    cv+=v[i]*j; 
 
 
 
    //与之前的物品相比  有无冲突 
    if (cw>c) 
        return FALSE; 
 
    //无冲突,添加至解路径 
    x[i]=j; 
 
    // 到此为止  0--i行 均无冲突 
    // 如果是最后一行  成功找到一个解 
    if(i==n){ 
 
        for(i=1;i<=n;i++) 
            printf("%d",x[i]); 
        if(cv>bestv) 
            bestv=cv; 
        printf("\n"); 
        return TRUE; 
 
    } 
 
    //如果不是最后一行 则判断i+1行 
 
    BOOL bSuit=FALSE; 
    for (int k=0;k<=1;k++) 
    {        
        //第i+1行存在合适位置  
        if (TestNode(i+1,k)) 
            bSuit=TRUE;  
    } 
 
   return bSuit; 
 

 
 
 
void  Bag() 
补充:软件开发 , C++ ,

CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,