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