回溯法求01背包问题(共6页).doc

精选优质文档-倾情为你奉上实验题目给定n种物品和一个容量为C的背包，物品i的重量是wi，其价值为vi，0/1背包问题是如何选择装入背包的物品（物品不可分割），使得装入背包中物品的总价值最大?实验目的（1）掌握回溯法的设计思想；（2）掌握解空间树的构造方法，以及在求解过程中如何存储求解路径；（3）考察回溯法求解问题的有效程度。实验内容（包括代码和对应的执行结果截图）#includeusing namespace std;int n,c,bestp; /物品的个数，背包的容量，最大价值int p100,w100,x100,bestx100; /物品的价值，物品的重量，xi暂存物品的选中情况,物品的选中情况void Backtrack(int i,int cp,int cw) /cw当前包内物品重量，cp当前包内物品价值 int j; if(in)/结束回溯 if(cpbestp)