背包问题的探讨

Research on Knapsack Problem

本文引入背包问题的一个实例,该实例的解法及其条件变化引起的求解程度难易的变化在文献[1]中已经提出,但文献[1]中只是简单指出几种特殊条件变化下求解的变化情况,而没有论证一般性结论.本文在此基础之上,对该实例作进一步研究,在改变实例中约束条件的情况下,给出求解过程;并找出了引起求解过程难易程度变化的原因.

This text introduces one example of Knapsack problem. The example＇s solution and the varieties of conditions have been pointed out in the literature. However,they have not drawn a perfect conclusion. This text is on the basis of it, and goes to engage in further study of it. Under changing the bounding - conditions of example, we give the solution. The reason of varieties of solution has been founded ： the varieties depend on the foundamental equation of dynamic programming. If the conditions satisfy the equation, the solution will be easy, or it will be hard and it is needed to add necessary information.