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

作者：刘玉娟; 王相海

来源：计算机应用研究, 2006, (01): 28-30.

• 0-1背包
• 扩展形式
• 动态规划
• 贪心算法 0-1 Knapsack
• Expanding Form
• Dynamic Programming
• Greedy Algorithm

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

• 单位
  信息安全国家重点实验室; 中国科学院研究生院; 辽宁师范大学