0-1背包问题（子集树回溯法）

问题描述
略

可行性约束函数：

限界函数： Bound()

只考虑约束函数，即背包里的物品重量之和小于背包容量

代码

#include <iostream>
using namespace std;
int C,n,w[100],v[100];
int BestX[100];    //BestX[i]=1代表物品i放入背包,0代表不放入
int CurValue=0;    //当前放入背包的总价值
int CurWeight=0;   //当前放入背包的总重量
int BestValue=0;   //最优值，当前的最大价值
int x[100];        //记录当前这轮回溯解的情况,x[i]=1代表物品i放入背包,0代表不放入
void backtrack(int t)
{
    if(t>n)   //走到叶子结点时,得到一组解的时候
    {
        if(CurValue>BestValue)  //如果当前背包里的总价值>最优值
        {
            BestValue=CurValue; //更新最优值
            for(int i=1;i<=n;i++)
               BestX[i]=x[i];   //将最优解更新
        }
    }
    else    //没有走到叶子结点时
    {
        if((CurWeight+w[t])<=C)   //如果当前物品能放入,进入左子树
        {
            x[t]=1;
            CurWeight+=w[t];
            CurValue+=v[t];
            backtrack(t+1);
            CurWeight-=w[t];     //记得回溯
            CurValue-=v[t];
        }
        x[t]=0;                  //进入右子树
        backtrack(t+1);
    }

}

int main()
{ 
   cin>>C>>n;
   for(int i=1;i<=n;i++)
      cin>>w[i];
   for(int i=1;i<=n;i++)
      cin>>v[i];
   backtrack(1);
   cout<<BestValue<<endl;
   for(int i=1;i<=n;i++)
      cout<<BestX[i]<<" ";
   return 0;
}

代码二：在考虑了可行性约束函数的情况下再考虑限界函数，详细代码见书

需要掌握的习题