1、实验目的
（1）掌握回溯法设计策略。

（2）通过0-1背包问学习回溯法法设计技巧2.实验内容
源程序：
#include<iostream>
using namespace std;
double c;//背包容量
int n; //物品数
double w[100];//物品重量数组
double p[100];//物品价值数组
double cw=0;//当前重量
double cp=0;//当前价值
double bestp=0;//当前最优值
double bound(int i)
{ double cleft,b;
//计算上界
cleft=c-cw;//剩余容量
b=cp;
//以物品单位重量价值递减序装入物品
while(i<=n&&w[i]<=cleft)
{
cleft-=w[i];
b+=p[i];
i++;
}
//装满背包
if(i<=n)
b+=p[i]*cleft/w[i];
return b;
}
void Backtrack(int i)
{
if(i>n)
{
if(cp>bestp)
bestp=cp;
return;
}
if(cw+w[i]<=c) //搜索左子树
{
cw+=w[i];
cp+=p[i];
Backtrack(i+1);
cp-=p[i];
cw-=w[i];
}
if(bound(i+1)>bestp)//搜索右子树
Backtrack(i+1);
}
double Knapsack (double pp[],double ww[],double d) {
int i;
double TP=0,TW=0;
cw=0.0;cp=0.0;bestp=0.0;//计算所有物品的重量及价值
for(i=1;i<=n;i++)
{
TP=TP+pp[i];
TW=TW+ww[i];
}
if(TW<=d)//所有物品装入背包
bestp=TP;
else
{
Backtrack(1);
}
return bestp;
};
int main()
{
int i,j;
double t,a,x[100];
cout<<"请输入物品种类数和最大载重量："<<endl;
cin>>n;cin>>c;
cout<<"请输入各物品重量："<<endl;
for(i=1;i<=n;i++)
cin>>w[i];
cout<<"请输入各物品价值："<<endl;
for(i=1;i<=n;i++)
cin>>p[i];
//排序
for(i=1;i<=n;i++)
x[i]=p[i]/w[i];
for(i=1;i<=n;i++)
for(j=i+1;j<=n;j++)
if(x[i]<x[j])
{
t=x[i];
x[i]=x[j];
x[j]=t;
a=p[i];
p[i]=p[j];
p[j]=a;
a=w[i];
w[i]=w[j];
w[j]=a;
}
//排序结束
/////////////////////////////
Knapsack(p,w,c);
cout<<"结果："<<endl;
cout<<bestp<<endl;
return 0;
}
结果：。