问题的形式化描述 此问题的形式化描述为,给定c>0,wi>0,vi>0,1≤i≤n,要 求找出一个n元0-1向量 (x1,x2, .. ,xn),其中xi∈{0,1},使 得对wixi求和小于等于c ,并且对vixi求和达到最大。 因此,0-1背包问题是一个特殊的整数规划问题。 此时问题的解结构为一个n元组 (n元一维向量),而每个解分量 xi取自有限集合Si。 Si={0,1}则, |Si|=2,如果用穷举法求解问题则 需要分析2n种可能的情况,该算法 的时间复杂度为O(2n)。 算法设计与分析 5
m ax v i x i i 1
n
n w i x i c i 1 xi {0,1}, 1 i n 2013-5-24

计算机算法设计与分析第5章回溯法_工学_高等教育_教育专区。计算机算法设计与分析,课件第5章 回溯法 1 ?学习要点 ? 理解回溯法的深度优先搜索策略。 ? 掌握用...
算法设计与分析_第5章_回溯法_自然科学_专业资料。哈尔滨工程大学 算法课件算法设计与分析第5章 回溯法 1 学习要点理解回溯法的深度优先搜索策略 掌握用回溯法...
《算法设计与分析》-第五章 回溯法_工学_高等教育_教育专区。算法分析与设计 课件 山东轻工业学院计算机科学与技术专业上课所用回溯法(backtracking) 第五章 ...
算法设计与分析(第5章回溯法) 数学建模暑假培训数学建模暑假培训隐藏>> 第五章 回溯法 TraceBacking 2011-6-21 西安邮电学院 1 回溯法实际是一个类似枚举的...
《算法设计与分析》- 第 5 章 回溯法 - A 隐藏>> 算法设计与分析授课教师:刘伟电 邮话:15389070097 件:bme_liuwei@163.com liuwei@xupt.edu.cn QQ:...
计算机算法设计与分析(王晓东) 第5章 回溯法_互联网_IT/计算机_专业资料。第5章 回溯法 1 ? ? ? ? ? 学习要点 理解回溯法的深度优先搜索策略。 掌握用...
} 19. } 西安邮电大学计算机学院 第5章 回溯法 5.8 图的 m 着色问题本节要求理解解决图的 m 着色问题的回溯算法以及算法的效率,是本课程的重点。 问题的...
第5章 回溯法 1 ? ? ? ? ? ? ? 学习要点 理解回溯法的深度优先搜索策略。 掌握用回溯法解题的算法框架 (1)递归回溯最优子结构性质 (2)迭代回溯贪心选择...
第五章 算法设计与分析———回溯法 12/14/2012 1 回溯法 有许多问题,当需要找出它的解集或者要求回答 什么解是满足某些约束条件的最佳解时,往往要使用 回溯...
《计算机算法设计与分析》PPT第五章 回溯法_互联网_IT/计算机_专业资料。第5章 回溯法 1 ? 学习要点 ? 理解回溯法的深度优先搜索策略 ? 掌握用回溯法解题的...
热门文档