算法设计与分析 综合性实验报告

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为整数 都较大的情形 随机产生n个物品的重量向量wi 1< wi< 100 wi为整数 和价值向量vi 1< vi< 100 vi为整数 0 1背包问题可以用许多方法来求解 有些算法可以得到问题的精确最优解 有些仅能获得一个近似最优解 本综合设计性实验要求用3种以上的方法求解0 1背包问题 获得精确最优解或近似最优解皆可 并对所采用的多种算法从运行时间 寻找是否为最优解 能够求解的问题规模等方面进行对比和分析 本课程讲述的所有算法思想都可以用来求解此问题 甚至本课程未涉及的许 多算法也非常适合于求解此问题 学生可以先尝试先用本课程已介绍的算法来实现和分析 学有余力或兴趣驱动下可以寻找一些智能算法的资料来试一试 涉及的方法可以有：蛮力求解 递归求解 动态规划求解 贪心求解 回溯法求解 广度优先的分支限界法求解 优先队列的启发式分支限界法 遗传算法 模拟退火算法 蚁群算法 粒子群算法等 ">0 1背包问题是一例典型的组合优化的NP完全问题 问题可以描述为：给定一组共n个物品 每种物品都有自己的重量wi i 1 n和价值vi i 1 n 在限定的总重量（背包的容量C）内 如何选择才能使得选择物品的总价值之和最高 选择 [更多] 多算法也非常适合于求解此问题 学生可以先尝试先用本课程已介绍的算法来实现和分析 学有余力或兴趣驱动下可以寻找一些智能算法的资料来试一试 涉及的方法可以有：蛮力求解 递归求解 动态规划求解 贪心求解 回溯法求解 广度优先的分支限界法求解 优先队列的启发式分支限界法 遗传算法 模拟退火算法 蚁群算法 粒子群算法等 ">0 1背包问题是一例典型的组合优化的NP完全问题 问题可以描述为：给定一组共n个物品 每种物品都有自己的重量wi i 1 n和价值vi i 1 n 在限定的总重量（背包的容量C）内 如何选择才能使得选择物品的总价值之和最高 选择 [更多]