| 0-1背包问题的两种扩展形式及其解法* |
| |
| 引用本文： | 刘玉娟,王相海.0-1背包问题的两种扩展形式及其解法*[J].计算机应用研究,2006,23(1):28-30. |
| |
| 作者姓名： | 刘玉娟 王相海 |
| |
| 作者单位： | 1. 辽宁师范大学,计算机与信息技术学院,辽宁,大连,116029
2. 辽宁师范大学,计算机与信息技术学院,辽宁,大连,116029;中国科学院,研究生院,信息安全国家重点实验室,北京,100039 |
| |
| 基金项目： | 中国科学院资助项目;辽宁省自然科学基金;辽宁省大连市科技计划;辽宁省高等学校中青年学科带头人基金 |
| |
| 摘 要： | 0-1背包问题是经典的NP-HARD组合优化问题之一，由于其难解性，该问题在信息密码学和数论研究中具有极其重要的应用。首先对01背包问题及其解法进行了分析，然后提出01背包问题的两种扩展形式，并给出了基于动态规划和贪心算法的两种有效算法来解决这两类问题。实验结果验证了所提出方法的有效性。
|
| 关 键 词： | 0-1背包 扩展形式 动态规划 贪心算法 |
| 文章编号： | 1001-3695(2006)01-0028-03 |
| 收稿时间： | 2004-11-21 |
| 修稿时间： | 2005-06-28 |
Two Kinds of Expanding Forms of 0-1 Knapsack Problem and Its Solution Methods |
| |
| LIU Yu-juan,WANG Xiang-hai.Two Kinds of Expanding Forms of 0-1 Knapsack Problem and Its Solution Methods[J].Application Research of Computers,2006,23(1):28-30. |
| |
| Authors: | LIU Yu-juan WANG Xiang-hai |
| |
| Abstract: | The 0-1 knapsack problem is a classic NP-Hard problem in the combinational optimization. Because it is very hard for the solution , it is very important in the research on cryptosystem and number theory . In this paper, the 0-1 knapsack problem and its algorithm is analyzed firstly. And then this paper presents two kinds of expand form, and proposed two efficient algorithms based on dynamic programming and greedy algorithm to solve the proposed problems. Simulation results show it is effective, |
| |
| Keywords: | 0-1 Knapsack Expanding Form Dynamic Programming Greedy Algorithm |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《计算机应用研究》浏览原始摘要信息 |
|
点击此处可从《计算机应用研究》下载全文 |
