pan.Baidu.com/s/1w-VSM WMR9ntewwdxzod4yw
代码： jnlh
算法分析与设计
时间
2020.5.16
实验名称
用回溯法求解0-1背包问题
实验的目的
要求通过上机实验，掌握回溯算法的问题描述、算法设计思想和编程。
实验原理
给出任意组数据，利用回溯算法的局限性和剪枝思想，求解0-1背包问题并输出答案。
实验步骤
问题分析：
给你n种物品和背包。 物I的重量为wi0，其价值为vi0，背包的容量为c。 为了使放在背包里的东西的总价值最大化，应该怎么选择放在背包里的东西？ (要求使用回溯法)
书中例题：
手动求解应选择1、3、4三个项目，最优值为20；
算法思想：01背包是一个寻找最优解的问题，需要用回溯法构造解的子集树。 对于每个项目I，只有对该项目选择或不选择两个决策，总共有n个项目，可以依次考虑各个项目，由此形成求解空间的树；
基本的想法是遍历这棵树，列举所有情况，最后判断，如果重量不超过背包的容量，价值最大，这个方案就是最后的答案。
搜索状态空间树时，如果左子节点是可行节点，则搜索进入该左子树。 在右子树的情况下，首先计算上边界函数，判断是否拉（剪枝）。
http://www.Sina.com/bound(:现值cw剩余容量中的最大价值=当前最佳价值bestp。
为了很好地计算和运用上界函数，要进行剪枝，首先选择物品按其单位重量价值从大到小的顺序排序，然后依次考虑各物品。
上界函数从文件中读取用例数据，初始化数据；
物品按单位重量价值从大到小排序
操作以下：
用回溯法试制了求0-1背包问题解的算法，即算法步骤：，即求放或不放n件物品之一的方案
在此，Xi=0或者1，Xi=0表示物体I不放入背包，Xi=1表示物体I放入背包。
从第0层开始进行递归函数Backtrack，
in时，算法搜索叶子节点，得到新物品的包装方案，
此时算法适时更新当前的最优价值和最优解；当i<n时，当前扩展结点位于排列树的第（i-1）层，此时算法选择下一个要安排的物品，以深度优先方式递归的对相应的子树进行搜索，对不满足上界约束的结点，则剪去相应的子树。
④当整个解空间树遍历完成则输出最优值与最优解；
关键代码
关键代码（带注释） 1. 初始化函数init（）
输入背包容量、物品总数、物品价值重量等数据，求出每一个物品的单位重量的价值，根据该单价进行从大到小的排序；
2. 求上界函数bound（用于剪枝）按照剩余物品的单价将背包的剩余容量塞满（可塞一个物品的一部分），塞满后的背包内的物品总价值即为上界，若该上界小于当前最优值则剪枝；
3. 计算时间部分代码通过时间函数QueryPerformanceFrequency与cpu的主频频率得到程序段的运行时间，可以精确到微妙，比clock函数更精确一些；
4. 随机数生成程序利用rand（）函数生成大小为10、100、1000的三个文件，其中全为随机数；
3、4两个部分与之前的实验所用方法相同；
5. 回溯函数（核心部分）如果当前层达已处理完最后一个物品，则说明当前的价值比现在的最优值要大，因此更新最优值与最优解；
如果当前层未处理完最后一个物品，则如果当前物品可放入背包则直接进入左子树，如果右子树（不放入当前物品）的上界大于当前最优值则可以进入右子树；
测试结果
运行结果截图及分析
对于课本样例：
运行结果正确；
对于三种不同规模的文件（10、100、1000）：
可以看到对三种规模的文件进行测试的结果，数据规模越大则时间越长；
因为剪枝的原因看不出其O（2^n）的时间复杂度；
时间复杂度分析：
该问题为回溯法的子集树问题，对每一个物品都有放入与不放两种决策，因此遍历解空间树的时间复杂度未O(2^n);
实验心得
通过这次实验，我回顾了回溯算法的基本原理，回溯法的剪枝与限界方法在本问题中有着清晰简洁的体现，加深了我对它们的使用的熟练度。为更难更深层次的问题的回溯法求解打下基础。