背包问题计算凸现winqsb软件设计模块中的一个缺陷

Knapsack Problem Highlights a Flaw in the Design Calculation Module in WINQSB

背包问题(Knapsack problem)是一种组合优化的NP完全问题,是运筹学问题中比较典型的问题.有一些简单的一维背包问题可以既可以用动态规划模型来求解,也可以用线性规划模型的方法来求解,因此我们可以借助运筹学专门计算软件winqsb2.0来进行辅助计算,但是在有些背包问题的求解中,使用这两种模型计算会出现不同的结果,本文就着重讨论这一现象,分析出现差异的原因.

Knapsack problem is a kind of combinatorial optimization problem of NP complete. It is typi- cal problem of operational research. There are some simple one--dimensional knapsack problems which can be solved by the method of dynamic programming model, and can be also solved by the method of line- ar programming model, so we can use the operational research special software ＂winqsb2.0＂ to calculate, but in solving some knapsack problem, using the two models will bring out different results. This paper discusses this phenomenon, and analyzes the causes of the difference.