3个变形背包问题的形式化推导

在对0-1背包问题的若干变形问题进行深入研究的基础上,使用二进制数组的方式形式化描述了几种背包问题的程序规约,通过程序规约变换技术获取问题求解的递推关系,给出了3个变形背包问题的算法推导过程,有效保证了算法程序的可靠性,并可将采用的推导方法在子集和问题、船装载等问题中加以推广应用.

The Formal Derivation of Three Forms of 0-1 Knapsack Problems

Based on depth study of various forms of knapsack problem in this paper,a vector of binary variables to describe program specification of various forms of knapsack problem formally has been used.Through program specification conversion technology,the recurrence relation of problem solving sequence which can solve various forms of knapsack problems has been used,based on which obtained their algorithm programs.Through this way,the reliability of the algorithm program is.guaranteed.The derivation methods that is used in this paper can also be applied in subset-sum problems,ship-loading problems and so on.