实验4 回溯法解0-1背包问题
一、实验要求
1．要求用回溯法求解0-1背包问题；
要求交互输入背包容量，物品重量数组，物品价值数组；2．要求显示结果。

3．
二、实验仪器和软件平台
仪器：带usb接口微机
软件平台：WIN-XP + VC++
三、实验源码
#include \
#include<iostream>
#include<cstdio>
#include<>
#include<iomanip>
using namespace std;
template<class ty>
class Knap
{
public:
friend void Init();
friend void Knapsack();
friend void Backtrack(int i);
friend float Bound(int i);
bool operator<(Knap<ty> a)const
{
if(fl< return true;
else return false;
}
private:
ty w; ;
cout<<endl;
潣瑵?请依次输入?渼?个物品的价值P:<<endl;
for(i=0;i<n;i++)
cin>>bag[i].v;
for(i=0;i<n;i++)
{
bag[i].flag=0; bag[i].kk=i;
bag[i].fl=*bag[i].v/bag[i].w;
}
}void Backtrack(int i){cw+=bag[i].w;if(i>=n) <=c) lag=1;
cp+=bag[i].v; Backtrack(i+1);
cw-=bag[i].w; cp-=bag[i].v;
}
if(Bound(i+1)>bestp)lag=0; Backtrack(i+1);
}}<=cleft){;
b+=bag[i].v;
i++;
}
/bag[i].w * cleft;
return b;
}
void Knapsack() k]=bag[k].flag; lag*bag[k].v; //价值累加
}
cout<<endl;
潣瑵? 当前最优价值为:<<L<<endl;
潣瑵? 变量值x = ;
for(int i=1;i<=n;i++)
{
cout<<x[i-1];}delete []bag; bag=NULL;x=NULL; delete []x;
getch(); cout<<endl;
}int main()
{cout<<endl;cout<<|**********背包问题0-1 回溯法解**********|<<endl;Init(); Backtrack(0);Knapsack();return 0;
}
四、运行结果
五、实验小结
通过该实验，我充分了解了回溯法与分支界限法的区别。

回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。

算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。

如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。

．。