0-1背包问题的两种扩展形式及其解法

被引：14

作者：

刘玉娟

王相海

机构：

[1] 辽宁师范大学计算机与信息技术学院

来源：

关键词：

0-1背包; 扩展形式; 动态规划; 贪心算法;

D O I：

暂无

中图分类号：

TN918.1 [理论];

学科分类号：

070104 ;

摘要：

0-1背包问题是经典的NP-HARD组合优化问题之一,由于其难解性,该问题在信息密码学和数论研究中具有极其重要的应用。首先对0-1背包问题及其解法进行了分析,然后提出0-1背包问题的两种扩展形式,并给出了基于动态规划和贪心算法的两种有效算法来解决这两类问题。实验结果验证了所提出方法的有效性。

引用

页码：28 / 30

页数：3