Question

回溯法解决0-1背包问题，不能输出最优解，大家帮我看看，谢谢

代码如下：
#include <iostream>
#include <fstream>
#define N 100
using namespace std;
int n;double weight;//n,weight分别代表物品数量和背包载重量
double v[N],w[N];//v[N],w[N]分别存放物品的价值和重量
double cw=0,cv=0,bestv=0,bestw=0;//cw,cv,bestv分别代表当前重量，当前价值，最优价值
bool bestChoice[N],currentChoice[N];//标记物品是否选中
//从文本文件里面读取背包信息
void ReadData()
{
ifstream ifs("input.txt",ios::in);
ifs>>n>>weight;
for(int i=1;i<=n;i++)
{
ifs>>w[i]>>v[i];
}
}
void BackTrack(int i)
{
int k;
double Bound(int i);
for(k=1;k<=n;k++)
currentChoice[k]=false;
if(i>n)
{//到达叶子节点
if(cv>bestv)
{
bestv=cv;
bestw=cw;
for(int j=0;j<=n;j++)
bestChoice[i]=currentChoice[i];
}
return;
}
//搜索子树
if(cw+w[i]<=weight)
{//进入左子树
cw+=w[i];
cv+=v[i];
currentChoice[i]=true;
BackTrack(i+1);
cw-=w[i];
cv-=v[i];
currentChoice[i]=false;
}
double r=Bound(i+1);
if(r>bestv)
BackTrack(i+1);//进入右子树
}
double Bound(int i)
{//计算上界
double cleft=weight-cw;//剩余容量
double bound=cv;
//以物品价值密度减序顺序装入物品
while(i<=n&&w[i]<=cleft)
{
cleft-=w[i];
bound+=v[i];
i++;
}
if(i<=n)
bound+=v[i]/w[i]*cleft;
return bound;
}
void ShowResult()//输出最优解
{
cout<<"装入背包物品的最大价值："<<bestv<<endl;
cout<<"装入背包物品的总重量："<<bestw<<endl;
cout<<"此时选择为w[i] v[i]";
for(int i=1;i<=n;i++)
{
if(bestChoice[i]==1)
cout<<w[i]<<" "<<v[i]<<endl;
}
}
void main()
{

ReadData();
BackTrack(1);
ShowResult();
}

Answer 1

gmk