[1]游 颖,杨庆红,齐蕾蕾.3个变形背包问题的形式化推导[J].江西师范大学学报(自然科学版),2017,(02):116-121.
　YOU Ying,YANG Qinghong,QI Leilei.The Formal Derivation of Three Forms of 0-1 Knapsack Problems[J].Journal of Jiangxi Normal University:Natural Science Edition,2017,(02):116-121.
点击复制

3个变形背包问题的形式化推导()
分享到：

《江西师范大学学报》（自然科学版）[ISSN:1006-6977/CN:61-1281/TN]

卷:
期数:
2017年02期
页码:
116-121
栏目:
出版日期:
2017-03-01

文章信息/Info

Title:
The Formal Derivation of Three Forms of 0-1 Knapsack Problems
作者:
游 颖; 杨庆红; 齐蕾蕾
江西师范大学计算机信息工程学院,江西 南昌 330022
Author(s):
YOU Ying; YANG Qinghong; QI Leilei
College of Computer Information Engineering,Jiangxi Normal University,Nanchang Jiangxi 330022,China
关键词:
形式化推导;  0-1背包问题;  二进制向量;  程序规约;  递推关系
Keywords:
formal derivation;  0-1 knapsack problem;  vector of binary;  program specification;  recurrence relation
分类号:
TP 311.5
文献标志码:
A
摘要:
在对0-1背包问题的若干变形问题进行深入研究的基础上,使用二进制数组的方式形式化描述了几种背包问题的程序规约,通过程序规约变换技术获取问题求解的递推关系,给出了3个变形背包问题的算法推导过程,有效保证了算法程序的可靠性,并可将采用的推导方法在子集和问题、船装载等问题中加以推广应用.
Abstract:
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.

参考文献/References:

[1] 田烽楠,王于.求解0-1背包问题算法综述 [J].软件导刊,2009,8(1):59-61.
[2] 王蔚,邱伟星.整数的带余除法在子集和问题中的应用 [J].计算机工程,2011(s1):183-185.
[3] 刘玉娟,王相海.0-1背包问题的两种扩展形式及其解法 [J].计算机应用研究,2006,23(1):28-30.
[4] 程跃.多背包问题的一种求解方法 [J].产业与科技论坛,2011,10(20):184-185.
[5] 孙瑞芳,焦晓君,施瑞娜,等.分支限界装载问题的算法分析与设计 [J].软件设计开发,2015(3):72-76.
[6] 杨庆红,肖燕娟.一种高效的算法程序设计方法:PAR方法 [J].计算机与现代化,2000(6):1-5.
[7] 石海鹤,薛锦云.一种基于PAR的高可靠算法程序设计技术 [C].第六届中国测试学术会议论文集,2010:433-437.
[8] 石海鹤,薛锦云.基于PAR的算法形式化开发 [J].计算机学报,2009,32(5):982-991.
[9] Yang Qinghong.An algorithmic formalization mnthod based on recurrence technique [C].The 8th International Conference on Computer Science & Education,2013.
[10] Xue Jinyun.A unified approach for developing efficient algorithmic programs [J].Journal of Computer Science and Technology,1997,12(4):314-329.
[11] 胡启敏,薛锦云.若干算法程序的形式化推导与生成技术研究 [J].计算机研究与发展,2008,45:148-153.
[12] 王昌晶,薛锦云.算法及其时间复杂度可同步形式化推导的方法 [J].计算机应用研究,2008(3):681-683.
[13] 石海鹤,揭安全,薛锦云.0-1背包问题的一种新解法 [J].计算机工程,2008,34(17):37-49.
[14] 王昌晶,薛锦云.一类0-1背包问题算法程序的形式化推导 [J].武汉大学学报:理学版,2009,55(6):674-680.
[15] 石海鹤.基于PAR的排序算法自动生成研究 [J].软件学报,2012(9):2248-2260.

备注/Memo

备注/Memo:
收稿日期:2016-10-22基金项目:国家自然科学基金(61363013)资助项目.通信作者:杨庆红(1968-),女,江西南昌人,教授,主要从事软件形式化和智能教育软件的研究.E-mail:yangqh120@163.com
更新日期/Last Update: 1900-01-01