01Package

本来是准备全部拿C写的,但分支界限法要用的队列实在不想写了,所以改成了C++

请利用穷举法、自顶向下的备忘录法、动态规划算法、回溯法、分支限界法、蒙特卡洛来求解0-1背包问题, 比较不同算法的时间复杂度和空间复杂度。关于0-1背包问题描述如下: 有一个包和n个物品,包的容量为m,每个物品都有各自的体积和价值, 问当从这n个物品中选择多个物品放在包里而物品体积总数不超过包的容量m时, 能够得到的最大价值是多少?[对于每个物品不可以取多次,最多只能取一次,之所以叫做01背包,0表示不取,1表示取] 实验细节:

  1. 语言不限,要求将6种算法实现为6个函数,并在测试时一次性全部输出结果;
  2. 测试数据在附件的压缩包中。