《01背包问题(回溯法).pdf》由会员分享，可在线阅读，更多相关《01背包问题(回溯法).pdf（5页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、 0-1 背包问题(回溯法)实验报告 姓 名：学 号：指导老师：一算法设计名称：0-1 背包问题（回溯法）二.实验内容 问题描述:给定n 种物品和一背包。物品i 的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?在选择装入背包的物品时，对每种物品i 只有两种选择，即装入背包或不装入背包。不能将物品装入背包多次，也不能只装入部分的物品。三.实验目的 1.运用回溯思想，设计解决上述问题的算法，找出最大背包价值的装法。2.掌握回溯法的应用 四算法设计：问题求解思路 1.由 0-1 背包问题的最优子结构性质，建立计算mij的递归式如下：iiiwjw
2、jjimivwjimjimjim0,1,1,1max),(2.查找装入背包物品的回溯函数：从0-1 二叉树的根开始搜索：若是叶子节点，则判断此时的价值是否比当前最优的价值大，否则将之替换，并获得最优解向量且返回；若不是叶子节点，则向左右子树搜索，先改变当前的数据状态，递归的调用自己，然后恢复数据状态表示回溯。3.边界函数bound 主要是当还未搜索到叶子节点时，提前判断其子树是否存可能存在更优的解空间，否则进行回溯，即裁剪掉子树的解空间。关键数据结构及函数模块：（Backtrack.h）#ifndef _BACKTRACK_H_#define _BACKTRACK_H_ class BP_01
3、_P public:niiixv1maxnixCxwiniii1,1,01 BP_01_P(int w,int n):m_Sum_weitht(0),m_Number(0)m_Sum_weitht=w;m_Number=n;bestHav=0;bestVal=0;curVal=0;curHav=0;m_hav=new intn;m_val=new intn;temop=new intn;option=new intn;BP_01_P()delete m_hav;delete m_val;delete temop;delete option;void traceBack(int n);int b
4、ound(int n);void printBestSoulation();int*m_hav;/每个物品的重量 int*m_val;/每个物品的价值 int*temop;/01 临时解 int*option;/01 最终解 int bestHav;/最优价值时的最大重量 int bestVal;/最优的价值 int curVal;/当前的价值 int curHav;/当前的重量 private:int m_Sum_weitht;/背包的总容量 int m_Number;/物品的种类;#endif _BACKTRACK_H_ 五：主要的算法代码实现：（Backtrack.cpp）边界函数：bo
5、und()int BP_01_P:bound(int n)int hav_left=m_Sum_weitht-curHav;int bo=curVal;while(nm_Number&m_havn=hav_left)hav_left-=m_havn;bo+=m_valn;n+;if(n=m_Number)if(curVal=bestVal)bestVal=curVal;for(int i=0;in;i+)optioni=temopi;return;if(curHav+m_havnbestVal)/向右子树搜索 temopn=0;/标记要丢弃这个物品 traceBack(n+1);主控函数：(m
6、ain.cpp)#include#include Backtrack.h using namespace std;int main()int number,weigth;coutweigth;coutnumber;BP_01_P*ptr=new BP_01_P(weigth,number);cout各种物品的重量:endl;for(int i=0;iptr-m_havi;cout各种物品的价值:endl;for(i=0;iptr-m_vali;ptr-traceBack(0);ptr-printBestSoulation();cout总重量:bestHavt 总价值:bestValendl;return 0;六：算法分析 采用回溯法解决0-1 背包问题，明显比动态规划法更优良。其主要表现在回溯法对解空间的界定上即裁剪，从而减少了搜索解空间的时间复杂度。当物品种类（0-1 树的深度）增大时可以明显感受到算法的时间性能。