回溯法的应用- 0-1 背包问题

实验内容 ：

        本实验要求基于算法设计与分析的一般过程（即待求解问题的描述、算法设计、算法描述、算法正确性证明、算法分析、算法实现与测试），通过回溯法的在实际问题求解实践 中，加深理解其基本原理和思想以及求解步骤。求解的问题为 0-1 背包。作为挑战：可以考虑回溯法在如最大团、旅行商、图的 m 着色等问题中的应用。

实验目的：

        ◆ 理解回溯法的核心思想以及求解过程（确定解的形式及解空间组织，分析出搜索 过程中的剪枝函数即约束函数与限界函数）；

        ◆ 掌握对几种解空间树（子集树、排列数、满 m 叉树）的回溯方法；

        ◆ 从算法分析与设计的角度，对 0-1 背包等问题的基于回溯法求解有进一步的理解。

实验步骤：

        步骤 1：理解问题，给出问题的描述。

        给定 n 种物品和一背包。物品 i 的重量是 wi>0，其价值为 vi>0，背包的容量为 c。 问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大。

        步骤 2：算法设计，包括算法策略与数据结构的选择；

        利用回溯法试设计一个算法求出 0-1 背包问题的解，也就是求出一个解向量ｘi （即 对 n 个物品放或不放的一种的方案）。其中， (ｘi = 0 或１，ｘi = 0 表示物体ｉ不放入背包，ｘi ＝1 表示把物体ｉ放入背包）。

        在递归函数 Backtrack 中， 当 i>n 时，算法搜索至叶子结点，得到一个新的物品装包方案。此时算法适合更新 当前的最优价值。当 i

步骤 3：描述算法。采用源代码以外的形式（如伪代码、流程图等）来描述；

 

步骤 4：算法的正确性证明。这个环节，在理解的基础上对算法的正确性给予证明 ；

        在 0-1 背包问题中，解空间为：(x1,x2,...,xn), 如果当前结果 P1=(x1,x2,...,xn)是最优 解，那么 P2=(x1,x2,...,xn−1)的时候，也就是减少一个物品但不改变背包容量的时候， 可以想到 P2 依然是该问题的最优解。从子集树角度来看，也就是最后一层结点全部去 掉后的结果，那么当前结果也是最优的。 

步骤 5：算法复杂性分析，包括时间复杂性和空间复杂性；

        计算上界需要 O(n)时间，在最坏情况下有 O(2 ⁿ)个右儿子结点需要计算上界，故解 0-1 背包问题的回溯算法 backtrack 所需要的时间为 O(n2 ⁿ).

步骤 6：算法实现与测试。附上代码或以附件的形式提交，同时贴上算法运行结果截图；

        

#include
#includeusing namespace std;
class Knap {friend double knapsack(double *,double *,double ,int);
private:double Bound(int i) {//计算上界double cleft = c - cw; //剩余容量double 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) {//到达叶结点bestp = cp;return;}if (cw + w[i] <= c) { //进入左子树cw += w[i];cp += p[i];Backtrack(i + 1);cw -= w[i];cp -= p[i];}// float u=Bound(i + 1);// float bb=bestp;//当前的界是否大于背包当前的值if (Bound(i + 1) > bestp) { //进入右子树Backtrack(i + 1);}}double c; //背包容量int n; //物品数double *w; //物品重量数组double *p; //物品价值数组double cw; //当前重量double cp; //当前价值double bestp; //当前最优价值
};class Object {friend double knapsack(double *,double *,double,int);
public:int operator<=(Object a) const {return (d >= a.d);}
private:int ID;float d;
};
double knapsack(double p[], double w[], double c, int n) {//为 Knap: Backtrack 初始化double W = 0;double P = 0;Object * Q = new Object[n];for (int i = 1; i <= n; i++) {Q[i - 1].ID = i;Q[i - 1].d = 1.0 * p[i]/w[i];//cout<>p[i];}cout<<"请输入每件商品重量"<>w[i];}
}
int main(){double c;int n;cout<<"请输入背包容量:";cin>>c;cout<<"请输入物品数量:";cin>>n;    double p[n+1]={0};double w[n+1]={0};input(n,p,w);double m=knapsack(p,w,c,n);cout<<"此 0-1 背包问题的最优值为："<

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！