摘要
具有单连续变量背包问题（KPC）是标准0—1背包问题（0—1 KP）的一个新颖扩展形式，由于其中的背包载重不再固定不变，而是由一个连续变量进行连续调整，因此KPC是一个比0—1KP更难求解的背包问题．首先提出了一个带有实函数的变载重背包问题（0—1KP（∑，f）），基于动态规划法给出了求解它的一般方法；然后：利用放缩法将KPC中的连续变量离散化，在建立KPC的一个新数学模型的基础上，将它转化成为0—1KP（∑，f）的一个特例，利用0—1KP（∑，f）的求解方法给出了KPC的一个简单且易于实现的精确算法．
The knapsack problem with a single continuous variable （KPC） is a natural generalization of the standard 0-1 knapsack problem （0-1KP）. The capacity of knapsack in KPC is not fixed, but can be adjusted by a continuous variable. So it is more difficult to solve than 0-1KP. First of all, this paper presents a varying-capacity knapsack problem with real function （0-1KP（ Z ,f））, advances an exact algorithm for 0-1KP（ Z ,f） based on dynamic programming. Then, we discretize the continuous variables in KPC by scaling method, and establish a new mathematical model of KPC, which equivalently transforms KPC into a special case of 0-1KP（ Z ,f）. Thus, we propose an new exact algorithm for solving KPC.
作者
贺毅朝
张新禄
曲文龙
李宁
HE Yi-chao;ZHANG Xin-lu;QU Wen-long;LINing(College of Information and Engineering,Hebei GEO University,Shijiazhuang 050031,China;College of Mathematics and Information Science,Hebei Normal University,Shijiazhuang 050024,China)
出处
《数学的实践与认识》
北大核心
2018年第13期216-223,共8页
Mathematics in Practice and Theory
基金
国家自然科学基金(11471097)
河北省自然科学基金(F201640305)
河北省高等学校科学研究计划项目(ZD2016005)
关键词
NP完全问题
KPC问题
动态规划
放缩法
精确算法
NP-complete problem
KPC problem
dynamic programming
scaling method
exact algorithm
