当前位置 博文首页 > 爱新觉罗?炒饭的博客: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;
}
代码二:在考虑了可行性约束函数的情况下再考虑限界函数,详细代码见书
需要掌握的习题