实验3.回溯法的应用-0-1背包等问题.docVIP

实验4. 回溯法的应用- 0-1背包等问题 实验内容 本实验要求基于算法设计与分析的一般过程（即待求解问题的描述、算法设计、算法描述、算法正确性证明、算法分析、算法实现与测试），通过回溯法的在实际问题求解实践中，加深理解其基本原理和思想以及求解步骤。求解的问题为0-1背包。 作为挑战：可以考虑回溯法在其他问题（如最大团问题、旅行商、图的m着色问题）。 实验目的 理解回溯法的核心思想以及求解过程（确定解的形式及解空间组织，分析出有哪些信誉好的足球投注网站过程中的剪枝函数即约束函数与限界函数）； 掌握对几种解空间树（子集树、排列数、满m叉树）的回溯方法； 从算法分析与设计的角度，对0-1背包问题的基于回溯法求解有更进一步的理解。 环境要求 对于环境没有特别要求。对于算法实现，可以自由选择C, C++, Java，甚至于其他程序设计语言。 实验步骤 0-1背包; 步骤1： n个物品和1个背包。对物品i，其价值为vi，重量为wi，背包容量为W。如何选取物品装入背包，使背包中所装入的物品的总价值最大？ 在选择装入背包的物品时，对每种物品i只有两种选择，即装入背包或不装入背包。不能将物品装入背包多次，也不能只装入部分的物品。 约束条件： 目标函数： 步骤2： （1）物品有n种，背包容量为C，分别用p[i]和w[i]存储第i种物品的价值和重量，用 x[i]标记第i种物品是否装入背包，用bestx[i]存储第i种物品的最优装载方案； （2）用递归函数Backtrack (i,cp,cw)来实现回溯法有哪些信誉好的足球投注网站子集树（形式参数i表示递归深 度，n用来控制递归深度，形式参数cp和cw表示当前总价值和总重量，bestp表示当前最优总价值）： ① 若i n，则算法有哪些信誉好的足球投注网站到一个叶结点，判断当前总价值是否最优： 1 若cpbestp，更新当前最优总价值为当前总价值（即bestp=cp），更新 装载方案（即bestx[i]=x[i]( 1≤i≤n)）； ② 采用for循环对物品i装与不装两种情况进行讨论（0≤j≤1）： x[i]=j； 若总重量不大于背包容量（即cw+x[i]*w[i]=c），则更新当前总价 br= 值和总重量（即cw+=w[i]*x[i],cp+=p[i]*x[i]）, 对物品i+1调用递归函数Backtrack(i+1,cp,cw) 继续进行装载； 函数Backtrack(i+1,cp,cw)调用结束后则返回当前总价值和总重量 （即 cw-=w[i]*x[i],cp-=p[i]*x[i]）； 当j1时，for循环结束； ③ 当i=1时，若已测试完所有装载方案，外层调用就全部结束； （3）主函数调用一次backtrack(1,0,0)即可完成整个回溯有哪些信誉好的足球投注网站过程，最终得到的bestp和bestx[i]即为所求最大总价值和最优装载方案。 步骤3： BACKTRACK-KNAPSACK-01-REC(t,w,v,W) if t n //到达叶子结点 //如果找到多个解，那就择优 OUTPUT(x) //x[1..n]: 为问题的解，x[i]取值0或1 bestp = cp return if cw + w[t] = W //有哪些信誉好的足球投注网站左子树 x[t]=1 //x[1..n]: 为解向量，x[i]取值0或1 cw += w[t] //当前背包中物品的总重量 cp += v[t] //当前背包中物品的总价值 BACKTRACK-KNAPSACK-01-REC(t+1,w,v,W); cw -= w[t] cp -= v[t] if BOUND(t+1,W-cw,cp,w,v) bestp //有哪些信誉好的足球投注网站右子树 x[t]=0 BACKTRACK-KNAPSACK-01-REC(t+1,w,v,W) 计算上界： BOUND(i,cRemained,cp,w,v) //i为第i层。 //cRemained为背包的剩余容量，cp为当前背包中物品的总价值 b = cp while i = n w[i] = cRemained cRemained -= w[i] b += v[i] i ++ //装满背包 if i = n b += v[i] / w[i] * cRemained return b //cp+brp 步骤4：算法的正确性证明。需要这个环节，在理解的基础上对算法的正确性给予证明（这里可以略去。有兴趣可以深入一下“多米诺性质”）； 步骤5： 时间复杂度：O(2n) + O(n2n) = O(n2n)。 步骤6： #includestdio.h int n,c,bestp;//物品的个数，背包的容量，最