实验1 最大公约数（包括连续整除、欧几里得、分解质因数算法） 实验2 最近对问题（包括蛮力算法和分治算法） 实验3 最长公共子序列（包括动态规划法） 实验4 最大子段和问题（包括蛮力算法、分治算法和动态规划算法） 实验5 背包、01背包问题（包括贪心算法和分治算法） 实验6 n皇后_2009（包括回溯算法） 以上几个实验基本上都是采用不同的算法实现，所有代码均为原创。

对于学习遗传算法的同志们确实是一个参考的好资料！

本程序用python实现，采用动态规划算法实现0/1背包问题，并实现界面，装入背包的物品用红色背景显示。结果输出背包的最大价值。

这是算法设计与分析的一个基本的算法---蛮力法，通过全部遍历解决背包问题。

算法分析与设计课程的实验报告，关于0/1背包的各种算法解法，很详细，本人费时n久整理成功

1）一个简化的背包问题：一个背包能装总重量为 tota1_m，现有 n 个物件，其重量分别为（W1、W2、…、Wn）。问能否从这 n 个物件中挑选若干个物件放入背包中，使其总重量正好为 T ？若有解则给出全部解，否则输出无解。 1）输入要求：从键盘输入依次输入n种物体的重量w1、w2、…、wn和价值p1、p2、…、pn，输入背包总重量T。重量和价值在同一行。 2）功能要求：一个背包能装入物品的总重量为T，现有n种物品，每种物品若干件，每种物品的重量分别为w1、w2、…、wn，且每件对应的价值分别为p1、p2、…、pn。编写法实现从这n种物品中挑选若干件，每种物品根据自己的存货可选若干件，使其重量之和不超过T而走总价值最大。 3）01背包问题

回溯法求解 0/1 背包问题

5.算法改进 由m(i,j)的递归式容易证明，在一般情况下，对每一个确定的i(1≤i≤n)，函数m(i,j)是关于变量j的阶梯状单调不减函数。跳跃点是这一类函数的描述特征。在一般情况下，函数m(i,j)由其全部跳跃点惟一确定。如图所示。 对每一个确定的i(1≤i≤n)，用一个表p[i]存储函数m(i，j)的全部跳跃点。表p[i]可依计算m(i，j)的递归式递归地由表p[i+1]计算，初始时p[n+1]={(0，0)}。

LC 分枝限界/ FIFO 分枝限界法求解0/1 背包问题

0-1背包问题 一、实验目的 （1）掌握回溯法的设计思想； （2）掌握解空间树的构造方法，以及在求解过程中如何存储求解路径； （3）考察回溯法求解问题的有效程度。 二、实验内容 利用回溯法编程求解0-1背包问题，并对算法进行时间复杂性分析； TSP问题 一、实验目的 （1）掌握回溯法的设计思想； （2）掌握解空间树的构造方法，以及在求解过程中如何存储求解路径； （3）考察回溯法求解问题的有效程度。