1.实验目的
(1)掌握回溯法的处理思路与算法框架。
(2)掌握应用回溯法解决具体问题的方法。
(3)掌握回溯法的广泛应用。
2.实验内容
(1)问题描述
要求使用回溯法解决该问题。
(2)输入
(3)输出
3.问题实例分析
因此，先装入第一个物品，此时体积足够装入第二个物品。装完第二个物品后，还能在装第三个物品。以深度优先的顺序，此时访问到的解空间树的结点如图所示：
（注意：我自己都觉得图太丑了，大家画图时不要为了方便用wps自带的画图工具画！！！还是visio好！！！）
从该结点回溯到上一结点，并在访问右子树前分别计算每个结点的当前价值cp与剩余价值r，发现都可以将右子树直接剪枝剪掉。
4.算法描述及说明
正如第3节问题实例分析所述，算法的整体流程如下：
1.输入数据，并对每个物品进行编号。
2.计算每个物品的单位价值，并将物品按单位价值排序。
3.对于第i ii个物品，判断剩余体积是否能够装下该物品。
4.若能装下该物品，则将该物品装入，并构造相应结点。
5.若不能装入该物品，则不将该物品装入，考虑下一物品。
6.在第4步中的物品撤出背包，构造相应结点，并计算剩余物品能产生价值的上界。若上界大于当前最优解，则装入考虑下一物品，否则不考虑。
7.重复3-6的步骤，直到所有物品都被考虑过。
5.算法正确性分析
算法会正确地结束：在遍历完解空间后，找到了使总价值最大的解，算法会停止。
回溯法的正确性分析：开始时，根结点是解空间树唯一的活结点，也是当前的扩展结点。在这个扩展结点处，搜索向深度方向移至一个新节点。这个新结点成为新的扩展结点。如果在当前扩展结点处不能再向纵深方向移动，则当前扩展结点成为死结点。应回溯至最近的活结点处，使得这个活结点成为当前扩展结点。回溯法以系统的方式递归地在解空间树中进行搜索，直到找到所要求的解惑解空间中已无活结点。
因此，利用回溯法会系统地查找背包问题的所有可行解，在剪枝时利用限界函数与剪枝函数剪去了不可行的分支，保留了可行并能产生最大解的分支。
从而，该算法是正确的。
6.算法时间复杂性分析
7.运行结果展示及其说明
8.心得体会
9.程序源代码
#include<iostream> #include<algorithm> using namespace std; double cw;//当前重量 double cp;//当前价值 double bestp;//当前最优价值 int n;//物品数量 double c;//背包容量 const int N = 105; int x[N]; struct Bag { double w, v; int id, x; }; Bag bag[N]; bool cmp(Bag a, Bag b) { return (a.v / a.w) > (b.v / b.w); } double bound(int i) { double cleft = c - cw; double bd = cp; while (i <= n && bag[i].w <= cleft) { cleft -= bag[i].w; bd += bag[i].v; i++; } if (i <= n) bd += bag[i].v * cleft / bag[i].w; return bd; } void dfs(int i) { if (i > n) { bestp = cp; for (int i = 1; i <= n; i++) x[bag[i].id] = bag[i].x; return; } if (cw + bag[i].w <= c) { cw += bag[i].w; cp += bag[i].v; bag[i].x = 1; dfs(i + 1); cw -= bag[i].w; cp -= bag[i].v; bag[i].x = 0; } if (bound(i + 1) > bestp) dfs(i + 1); } int main() { cin >> n >> c; for (int i = 1; i <= n; i++) cin >> bag[i].w; for (int i = 1; i <= n; i++) cin >> bag[i].v; for (int i = 1; i <= n; i++) bag[i].id = i; sort(bag + 1, bag + 1 + n, cmp); dfs(1); cout << bestp<<endl; for (int i = 1; i <= n; i++) cout << x[i] << " "; return 0; }
