分支限界法综合

0 1背包问题是一例典型的组合优化的NP完全问题 问题可以描述为：给定一组共n个物品 每种物品都有自己的重量wi i 1 n和价值vi i 1 n 在限定的总重量（背包的容量C）内 如何选择才能使得选择物品的总价值之和最高 选择最优的物品子集放置于给定背包中 最优子集对应n元解向量 x1 …xn xi∈{0或1} 因此命名为0 1背包问题 0 1背包问题是许多问题的原型 但它又是一个NP完全问题 此实验主要研究和实现n 0< n< 200 和C C< 2000 C为整数 都较

主要讲解分治法、动态规划、贪心法、回溯法以及分支限界法等几种种经典的算法， 让同学们能够更进步了解算法的魅力所在。 在本章对每一种算法都是从算法的概念思想、计算框架以及算法应用案例实现逐一介绍， 让读者能够综合运用前面几章所学知识，进一步加深对算法的理解。