关于0-1背包问题的研究.pdfVIP

学兔兔 第3期(总第184期) 机 械 工 程 与 自动 化 No．3 2014年O6月 MECHANICAL ENGINEERING AUT0MAT10N Jun． 文章编号：1672—6413(2014)03—0221-03 关于O一1背包问题的研究米 王 雯，武 燕 (太原工业学院，山西 太原 030008) 摘要：阐述了0～1背包问题的概念，对主要的近似算法及精确算法进行了说明，并比较了它们各自的优点 和缺点，在此基础上提出了未来O一1背包算法的发展方向和趋势，并指出用粗糙集理论来解决O一1背包问 题的可能性。 关键词：背包问题；贪婪法；遗传算法；粗糙集理论 中图分类号：TB115 文献标识码：A 0 弓I言 0一l背包问题是指每类物件都有一件放人或者 背包问题是一种组合优化问题，具有较强的实际 不放人。设变量为 ，当物件i被放人时，则 =1；不 意义，从现实应用角度来看，货物的装箱问题、物资的 放入时，z ：0。其数学表达式为： 分配和存储问题等都可以用背包问题来解决。随着现 代网络的日益发展，在电子商务领域中，背包公钥密码 m ax ∑户 ． = 1 的应用也越来越广泛。但是当求解问题的数量较多 s．t． ：c {≤C z ∈{0，1)，i一1，2，…，，2． 时，最优解的求解还是比较困难，所以，对0—1背包问 = l 题进行算法研究或改进是一件很有必要的工作。 2 常规算法在求解0—1背包问题中的应用 传统求解背包问题的方法有近似算法和精确算 2．1 近似算法 法，其中，近似算法包括贪婪法、粒子群算法E13、遗传算 2．1．1 贪婪法 法、蚁群算法口 等；精确算法包括回溯法、动态规划法 贪婪法属于一种启发式算法，贪婪算法会以当前 等。精确算法存在空间及时间复杂性的问题，为克服 状况为基础作最优选择，容易忽略整体，但它可以在较 此缺点，用近似算法求解背包问题已经越来越受到人 短的时间内求到解，在很多情况下可以达到预期的目 们的关注。除了上述这几种常见的算法以外，还出现 的，缺点是该启发式算法不一定能够获得最优解。 了二进制差异演化算法L3]、知识进化算法 等新的算 贪婪策略对贪婪法求取最优解至关重要，常用的 法。还有粗糙集也可以用于解决背包问题，将粗糙集 贪婪策略有质量贪婪准则和价值密度贪婪准则、价值 理论引人遗传算法来解决背包问题，目的在于提高单 贪婪准则。这3种贪婪策略对背包的装入都是采用多 纯遗传算法的有哪些信誉好的足球投注网站效率，同时也可以改善解的质量。 步过程来完成的。贪婪法可以与其他算法相结合来解 1 o-1背包问题[5] 决背包问题，例如有杨婷婷、赵新超的更贪心粒子群算 背包问题可以这样理解：假设一位商人有一个容 法，对于大规模背包问题的求解非常有帮助；此外还有 量为 C公斤的背包，现在有 个重量和价值分别为 马杰良和刘茜提出的混合遗传算法嘲，贪婪算法可以 C 0和 O( 一1，2，…，7z)的物件，选择哪几个物件