CAJ | 학술논문

0—1背包问题是一种经典的NP-hard组合优化问题，现实生活中的很多问题都可以以它为模型。首先对0—1背包问题进行了描述，根据其具有最优子结构性质和子问题重叠性质，进而提出了基于动态规划法的策略来求解该问题。另外，为了降低算法的复杂性，又提出了算法的改进策略。实例的运行结果表明了算法的有效性，同时也证实了改进策略的优越性。
0—1배포문제시일충경전적NP-hard조합우화문제，현실생활중적흔다문제도가이이타위모형。수선대0—1배포문제진행료묘술，근거기구유최우자결구성질화자문제중첩성질，진이제출료기우동태규화법적책략래구해해문제。령외，위료강저산법적복잡성，우제출료산법적개진책략。실례적운행결과표명료산법적유효성，동시야증실료개진책략적우월성。
The 0 - 1 knapsack problem is a NP-hard problem, and many problems in real life can translate into it. Here 0 - 1 knapsack problem is described firstly, and then presents dynamic programming to solve the problem according to the properties of optimal substructure and sub-problem overlap. In addition, an improved algorithm is presented to decrease the complexity of the dynamic programming. Instance results show these algorithms are effective, and also confirm the improved algorithm is better.