课程报告
课程名称：算法设计与分析
专业名称：计算机科学与技术
学 号：
姓 名：
指导教师：
完成时间：20##年12月
目 录
一、设计目的....................................................... 3
二、设计内容....................................................... 3
2.1 整数背包问题简介............................................ 3
2.2 算法分析.................................................... 4
2.3 最优解存在证明.............................................. 4
三、穷举法求解整数背包问题......................................... 5
3.1 设计任务简介................................................ 5
3.2 问题的表示方案.............................................. 5
3.3 算法设计与描述.............................................. 5
3.4 算法实现与程序设计.......................................... 5
3.4.1编译环境............................................... 5
3.4.2 主要数据类型与变量.................................... 5
3.5 算法性能分析................................................ 6
四、动态规划法求解整数背包问题..................................... 6
4.1设计任务简介................................................ 6
4.2问题的表示方案.............................................. 6
4.3 算法设计与描述.............................................. 7
4. 4算法实现与程序设计......................................... 7
4.4.1 编译环境.............................................. 7
4.4.2 主要数据类型与变量.................................... 7
4.4.3 主要模块说明.......................................... 8
4.5 算法性能分析................................................ 8
五、回溯法求解整数背包问题......................................... 8
5.1 设计任务简介................................................ 8
5.2 回溯法中需确立的概念........................................ 9
5.3 问题的表示方案.............................................. 9
5.4 算法设计与描述.............................................. 9
5.5算法实现与程序设计......................................... 10
5.5.1 编译环境............................................. 10
5.5.2 主要数据类型与变量................................... 10
5.6算法性能分析............................................... 10
六、分支限界法求解整数背包问题.................................... 11
6.1 设计任务简介............................................... 11
6.2 问题的表示方案............................................. 11
6.3 算法设计与描述............................................. 11
6.4 算法实现与程序设计......................................... 12
6.4.1编译环境.............................................. 12
6.4.2 主要数据类型与变量................................... 12
6.4.3 主要模块说明......................................... 12
6.5 算法性能分析............................................... 12
七、测试结果与分析................................................ 13
7.1 测试数据................................................... 13
7.2测试结果................................................... 13
7.3结果分析................................................... 17
八、总结与讨论.................................................... 18
求解整数背包问题
一、设计目的
1）对0-1背包问题有更加深入的了解；
2）掌握穷举法、动态规划、回溯法、分支限界法的算法思想；
3）对BFS和DFS有进一步的了解；
4）了解穷举法、动态规划、回溯法、分支限界法在时间和空间上的消耗，比较它们在时间和空间上的复杂度。
5）提高自己的编程和思维能力
二、设计内容
2.1 整数背包问题简介
整数背包问题即0/1背包问题。对每种物品或者全取或者一点都不取，不允许只取一部分。现有n种物品，对1<=i<=n，已知第i种物品的重量为正整数Wi，价值为正整数Vi，背包能承受的最大载重量为正整数W，现要求找出这n种物品的一个子集，使得子集中物品的总重量不超过W且总价值尽量大。
2.2 算法分析
根据问题描述，可以将其转化为如下的约束条件和目标函数：
于是，问题就归结为寻找一个满足约束条件（1），并使目标函数
式（2）达到最大的解向量
。
2.3 最优解存在证明
首先证明一下0-1背包问题拥有最优解。
假设
是所给的问题的一个最优解，则
是下面问题的一个最优解：
。如果不是的话，设
是这个问题的一个最优解，则
，且
。因此，
，这说明
是所给的0-1背包问题比
更优的解，从而与假设矛盾。
三、穷举法求解整数背包问题
3.1 设计任务简介
设计求解整数背包问题的穷举算法，用穷举法解决0-1背包问题，需要考虑给定n个物品集合的所有子集，找出所有可能的子集（总重量不超过背包重量的子集），计算每个子集的总重量，然后在他们中找到价值最大的子集。
3.2 问题的表示方案
考虑给定n个物品集合的所有子集，找出所有可能的子集（总重量不超过背包重量的子集），计算每个子集的总重量，然后在他们中找到价值最大的子集。
3.3 算法设计与描述
枚举也所有可能的情况，找出其中的最大值。用N位二进制数来表示N件物品的选取情况，例如在N＝3的情况下 ‘000’代表未选取任何物品，而 ‘101’代表选取了第1件和第3件物品。因此将 0 ---- 2^n-1 的情况枚举，找也最大值即可。
3.4 算法实现与程序设计
3.4.1编译环境
DEV C++ 的环境下编写代码、运行实现。
3.4.2 主要数据类型与变量
vector
vector
int m_c; //背包的容量
int m_num; //物品的件数
int bestValue=0; //背包最大价值
int currentValue =0; //当前背包中物品的价值
int currentWeight =0; //当前背包中物品的重量
3.5 算法性能分析
穷举算法是时间复杂度最高的算法，算法的时间复杂度为 2^n, 并且要求（n<=32），所以算法的效率不高。但穷举算法是一种比较通用的算法，通常在找不到最佳的算法时，采用些算法。
四、动态规划法求解整数背包问题
4.1设计任务简介
设计求解整数背包问题的动态规划算法，即设计和实现整数背包问题的表示方案、动态规划递推算法，设计对算法或程序的测试方案并完成测试。
4.2问题的表示方案
0-1背包问题可以看作是寻找一个序列，对任一个变量
的判断是决定=1还是=0.在判断完
之后，已经确定了
，在判断时，会有两种情况：
（1） 背包容量不足以装入物品i，则=0，背包的价值不增加；
（2） 背包的容量可以装下物品i，则=1，背包的价值增加
。
这两种情况下背包的总价值的最大者应该是对判断后的价值。
令
表示在前i
个物品中能够装入容量为j
的背包的物品的总价值，则可以得到如下的动态规划函
数：
4.3 算法设计与描述
第一步，只装入第一个物品，确定在各种情况下背包能得到的最大价值；第二步，只装入前两个物品，确定在各种情况下的背包能够得到的最大价值；一次类推，到了第n步就得到我们所需要的最优解了。最后，
便是在容量为W的背包中装入n个物品时取得的最大价值。为了确定装入背包的具体物品，从的值向前寻找，如果>
,说明第n个物品被装入了背包中，前n-1个物品被装入容量为
的背包中；否则，第n个物品没有装入背包中，前n-1个物品被装入容量为W的背包中。依此类推，直到确定第一个物品是否被装入背包为止。由此，我们可以得到如下的函数：
.
4.4算法实现与程序设计
4.4.1 编译环境
DEV C++ 的环境下编写代码、运行实现。
4.4.2 主要数据类型与变量
int c[30][100];
//表示把前i个物品装入容量为j的背包中获得的最大价值
int x[30];//存放背包的选择情况
int w[100];//存放重量
int v[100];//存放价值
int m;//存放背包容量
int n;//存放物品数量
4.4.3 主要模块说明
int knapsack(int w[],int v[],int m,int n)
//求解背包可容纳的最大价值
4.5 算法性能分析
由于函数Knapsack中有一个两重for循环，所以时间复杂度为O[(n+1)x(m+1)].空间复复杂度也是O[(n+1)x(m+1)]，即O（nm）。
五、回溯法求解整数背包问题
5.1 设计任务简介
设计求解整数背包问题的回溯算法，首先要将问题进行适当的转化，得出状态空间树。 这棵树的每条完整路径都代表了一种解的可能。通过深度优先搜 索这棵树，枚举每种可能的解的情况；从而得出结果。但是，回溯法中通过构造约束函数，可以大大 提升程序效率，因为在深度优先搜索的过程中，不断的将每个解（并不一定是完整的，事实上这也就是构造约束函数的意义所在）与约束函数进行对照从而删除一些 不可能的解，这样就不必继续把解的剩余部分列出从而节省部分时间。
5.2 回溯法中需确立的概念
（1）约束函数：约束函数是根据题意定出的。通过描述合法解的一般特征用于去除不合法的解，从而避免继续搜索出这个不合法解的剩余部分。因此，约束函数是对于任何状态空间树上的节点都有效、等价的。
（2）状态空间树：刚刚已经提到，状态空间树是一个对所有解的图形描述。树上的每个子节点的解都只有一个部分与父节点不同。
（3）扩展节点、活结点、死结点：所谓扩展节点，就是当前正在求出它的子节点的节点，在DFS中，只允许有一个扩展节点。活结点就是通过与约束函数的对照，节点本身和其父节点均满足约束函数要求的节点；死结点反之。由此很容易知道死结点是不必求出其子节点的（没有意义）。
5.3 问题的表示方案
将问题进行适当的转化，得出状态空间树。 这棵树的每条完整路径都代表了一种解的可能。通过深度优先搜 索这棵树，枚举每种可能的解的情况；从而得出结果。
5.4 算法设计与描述
描述解的形式，
（1）定义一个解空间，它包含问题的所有解。
（2）构造状态空间树。
（3）构造约束函数（用于杀死节点）。
然后就要通过DFS思想完成回溯，伪代码如下：
void BackTrack(int depth)
{
if(depth > maxDepth) //已经到最大深度
{
if(solution is target)
save solution;
return;
}
for (int i =0;i { if(currentNode is searchable) //当前结点满足约束条件 { do something; BackTrack(depth+1); undo something; } } } 5.5算法实现与程序设计 DEV C++ 的环境下编写代码、运行实现。 vector vector int m_c; //背包的容量 int m_num; //物品的件数 int bestValue; //背包最大价值 int currentValue; //当前背包中物品的价值 int currentWeight; //当前背包中物品的重量
回溯法作为一种穷举方法，可以使用约束函数来排除一些不可能的结点。虽然不理论上此算法在理论上最坏的情况下，复杂度仍为2^n,但在实际实验中，其搜索效率比上一次使用的2进制枚举要高很多。 分枝界限可以说是dfs和bfs的结合，综合了DFS算法空间复杂度低和BFS时间复杂度低的优点。分枝界限法在回溯法的基础上更进了一步，在回溯法中， 一旦从问题状态空间树导出的解不满足约束函数，我们就将其分枝剪掉。在处理此类问题时，回溯法的思想可以进一步强化。在回溯法的基础上加上两个额外的条件 就变成了分支界限法 1. 对于一棵状态空间树的每一个结点所代表的部分解， 我们要提供一种算法，计算出通过这个部分解所繁衍也的任何解在目标函数上的最佳边界。 2. 目前所求得的最佳解 有了这两个条件，我们可以用当前求得的最佳解和所有结点的最佳边界比较，如果某结点的最佳边界不能超越当前最佳解（在求最大化问题中，该结点的最佳上界不大于当前最佳解，在求最小化问题中，该结点的最佳下界不小于当前最佳解），则将其剪掉。这就是分枝界限的主要相思。 分枝界限法在回溯法的基础上更进了一步，在回溯法中， 一旦从问题状态空间树导出的解不满足约束函数，我们就将其分枝剪掉。 利用贪心来确立上界函数。在搜索时，如果结点的最佳上界不大于当前最佳解，在求最小化问题中，该结点的最佳下界不小于当前最佳解），则将其剪掉。 DEV C++ 的环境下编写代码、运行实现。 int value; // 价格 int weight; // 重量 int ub; //价格上界 vector //物品选择，1表示选择，0表示未选择 struct Thing { int weight; int value; };//物品 int m_c; //背包的容量 int m_num; //物品的件数 vector bool myCmp2(const Thing& left,const Thing& other) //自定义比较函数 void CaculateUb(Node& node) //确定上界 int GetBestValue()//分支限界求最大价值 在使用限界分治法时，就是使用更好的限界剪枝函数使得不必要的解被剔除，但是在最坏情况下的解仍然是和回溯法是相同的。而且在最坏情况下有 第一组： 物品数目：7； 背包容量：18； 每个物品重量为：11 2 4 8 9 6 10； 每个物品价值为：7 8 8 12 13 4 14。 第二组：物品数目：10； 背包容量：50； 每个物品重量为：8 12 24 16 6 9 35 21 18 19； 每个物品价值为：34 32 56 67 54 32 45 56 46 70。 穷举法输出结果 测试数据1： 测试数据2： 动态规划法输出结果 测试数据1： 测试数据2： 回溯法输出结果 测试数据1： 测试数据2： 分支限界法输出结果 测试数据1： 测试数据2： 四种实现的算法中，只有分支限界法没能够得到预期的最优解。。从时间复杂度和空间复杂度分析可知，动态规划法的时间复杂度是最小的，但是同时它的空间复杂度又是最大的。这里就可以看出在设计算法的过程中要考虑它们的平衡问题。在时间要求比较快的情况下，我们就可以选择动态规划法；在空间要求比较高时，我们就可以使用穷举法或是分枝限界法等其他改进的穷举法。 各种算法在解背包问题时的比较如下表所示： 背包问题是NP完全问题。半个多世纪以来，该问题一直是算法与复杂性研究的热门话题。通过对0-1背包问题的算法研究可以看出，回溯法和分枝限界法等可以得到问题的最优解，可是计算时间太慢；动态规划法也可以得到最优解，当5.5.1 编译环境
5.5.2 主要数据类型与变量
5.6算法性能分析
六、分支限界法求解整数背包问题
6.1 设计任务简介
6.2 问题的表示方案
6.3 算法设计与描述
6.4 算法实现与程序设计
6.4.1编译环境
6.4.2 主要数据类型与变量
6.4.3 主要模块说明
6.5 算法性能分析
个结点需要计算上界，所以在最坏情况下的时间复杂度为。七、测试结果与分析
7.1 测试数据
7.2测试结果
7.3结果分析
八、总结与讨论
时，算法需要
的计算时间，这与回溯法存在一样的缺点——计算速度慢；采用贪心算法，虽然耗费上优于前者，但是不一定是最优解。在本次报告中参考了许多文献，自己对于动态规划、回溯、分支限界有了更深的了解。通过本次试验，了解了时空复杂度对算法的影响。对时间和空间在计算机中的权衡有了进一步的了解。同时对于算法的理解不断加深，在程序编写中可以将几个相关的算法混合使用，采用它们各自的优点。在上面的回溯法中结合BFS和DFS在时间和空间上的优点，改进而来。