基于改进动态规划算法求解有界背包问题的方法

摘要

本发明涉及背包问题求解技术领域，公开一种基于改进动态规划算法求解有界背包问题的方法，定义物品种类最大数为N，背包的最大容量为C，物品种类为i，0≤i≤N，每种物品的单个价值为vi，重量为wi，每种物品的个数为ki；定义一个(N+1)×(C+1)二维价值表f，背包容量为j，0≤j≤C；计算余数a，根据容量余数a对容量状态j进行分组，将拥有相同容量余数的容量状态j放在一组计算。根据余数对容量状态j进行分组，对传统动态规划递归公式进行了改进，减少了求解BKP过程带来的冗余计算，同时对改进后的算法进行并行化，随着数据量的增大，本发明比现有的算法拥有更好效率，可实现BKP的快速求解。

说明书

技术领域

本发明涉及背包问题求解技术领域，具体地，涉及一种基于改进动态规划算法求解有界背包问题的方法。

背景技术

背包问题(KP)是一种经典的组合优化问题，被证明是NP-hard。它在密码学、决策优化、任务调度、成本控制和货物装载中具有各种实际应用。KP有几个子问题，例如0-1背包问题(0-1KP)，有界背包问题(BKP)和无界背包问题(UKP)等。

对于BKP的求解方法，通常将BKP转换为具有多个有效解决方案的等效0-1KP进行求解，这是传统动态规划(DP)算法解决BKP(基本法)的核心概念。也就是说，BKP中每个物品类型i都会生成k

上述两种方法基本上是着重于将BKP转换为0-1KP求解，将N项实例(w

发明内容

本发明解决的技术问题在于克服现有技术的缺陷，提供一种可有效减少甚至消除冗余计算的基于改进动态规划算法求解有界背包问题的方法。

本发明的目的通过以下技术方案实现：

一种基于改进动态规划算法求解有界背包问题的方法，定义物品种类最大数为N，背包的最大容量为C，物品种类为i，0≤i≤N，每种物品的单个价值为v

进一步地，上述方法包括如下步骤：

S1.计算余数a＝j mod w

S2.在第s组计算中，起始令j＝a

S3.计算S2中背包容量为j时的潜在价值

创建一个键值对A，令A.profit＝profit，A.number＝b；

S4.将键值对A插入List Q中，判断List Q中First_pair.number+k

S5.判断键值对Former_pair.profit是否大于A.profit，若不满足条件，则删去前一个键值对，循环本步骤直到满足条件，其中Former_pair为A的前一个键值对；

S6.比较List Q中所有元素的profit，取出最大的profit，得到背包容量为j、物品i放入背包时的最大价值f

S7.判断第s组的任务是否结束，若已结束，则清空List Q，令s＝s+1，继续执行步骤S2～S7；

S8.待n组任务都结束后，得到物品i放入容量为C的背包时的最大价值f

并列进一步地，多个分组的计算任务并行执行。

更进一步地，所述方法包括如下步骤：

S1.计算余数a＝j mod w

S2.在第s个进程中，起始令j＝a

S3.计算S2中背包容量为j时的潜在价值

创建一个键值对A，令A.profit＝profit，A.number＝b；

S4.将键值对A插入List Q’中，判断List Q’中First_pair.number+k

S5.判断键值对Former_pair.profit是否大于A.profit，若不满足条件，则删去前一个键值对，循环本步骤直到满足条件，其中Former_pair为A的前一个键值对；

S6.比较List Q’中所有元素的profit，取出最大的profit，得到背包容量为j、物品i放入背包时的最大价值f

S7.比较在每个进程中获得的最大价值f

与现有技术相比，本发明具有以下有益效果：

根据余数对容量状态j进行分组，对传统动态规划递归公式进行了改进，减少了求解BKP过程带来的冗余计算，同时对改进后的算法进行并行化，随着数据量的增大，本发明比现有的算法拥有更好效率，可实现BKP的快速求解。

附图说明

图1为实施例1所述的基于改进动态规划算法求解有界背包问题的方法流程图；

图2为实施例2所述的基于改进动态规划算法求解有界背包问题的方法流程图；

图3为随着K

图4为随着N

具体实施方式

下面结合具体实施方式对本发明作进一步的说明，其中，附图仅用于示例性说明，表示的仅是示意图，而非实物图，不能理解为对本专利的限制；为了更好地说明本发明的实施例，附图某些部件会有省略、放大或缩小，并不代表实际产品的尺寸；对本领域技术人员来说，附图中某些公知结构及其说明可能省略是可以理解的。

实施例1

一种基于改进动态规划算法求解有界背包问题的方法(以下称为FBKP)，定义物品种类最大数为N，背包的最大容量为C，物品种类为i，0≤i≤N，每种物品的单个价值为v

计算余数a，根据容量余数a对容量状态j进行分组，将拥有相同容量余数的容量状态j放在一组计算，本实施例是顺序计算，因此第一组计算结束，下一组才会开始。

如图1所示，上述方法包括如下步骤：

S1.分组：计算余数a＝j mod w

S2.初始值的确定：在第s组计算中，起始令j＝a

S3.背包容量为j时的潜在价值计算：

创建一个键值对A，令A.profit＝profit，A.number＝b；

S4.将键值对A插入List Q中，判断List Q中First_pair.number+k

S5.判断键值对Former_pair.profit是否大于A.profit，若不满足条件，则删去前一个键值对，循环本步骤直到满足条件，其中Former_pair为A的前一个键值对；

S6.计算背包容量为j，物品i放入背包时的最大价值f

S7.判断第s组的任务是否结束，若已结束，则清空List Q，令s＝s+1，继续执行步骤S2～S7；

S8.待n组任务都结束后，得到物品i放入容量为C的背包时的最大价值f

S9.获得BKP的最优解：通过比较每种物品i装入容量为C的背包中获得的最大价值f

上述S6中计算最大价值f

在求解0-1KP时，每一个新的物品需要确定其是否存在于背包中，因此解决BKP时，公式(1)可以变为：

其中x

首先，对公式(2)变形为：

f

令j＝a+bw

对公式(4)进一步变形得：

f

其中a为容量j与w

实施例2

本实施例是在实施例1对容量状态j进行分组的基础上将多个分组的计算任务并行执行，首先同实施例1定义物品种类最大数为N，背包的最大容量为C，物品种类为i，0≤i≤N，每种物品的单个价值为v

具体地，如图2所示，本实施例的方法(以下称为FBKP parallel)包括如下步骤：

S1.计算余数a＝j mod w

S2.在第s个进程中，起始令j＝a

S3.对于第s个进程，计算将前i种物品装入容量为j(1≤j≤C)的背包中分别获得的潜在价值：

创建一个键值对A，令A.profit＝profit，A.number＝b；

S4.将键值对A插入List Q’中，判断List Q’中First_pair.number+k

S5.判断键值对Former_pair.profit是否大于A.profit，若不满足条件，则删去前一个键值对，循环本步骤直到满足条件，其中Former_pair为A的前一个键值对；

S6.比较List Q’中所有元素的profit，取出最大的profit，得到背包容量为j、物品i放入背包时的最大价值f

S7.比较在每个进程中获得的最大价值f

S8.获得BKP的最优解：通过比较每种物品i装入容量为C的背包中获得的最大价值f

本实施例所有的状态是根据其余数进行分组的，因此余数仿真循环是独立的，不同余数的状态之间不会互相装载写入，因此对余数循环进行并行化是可行的。并且每个处理器都需要维护一个私有List Q以支持计算，并且在开始新的余数组之前，应该清除一次List Q。当wi个任务完成并同步后，下一项才可以更新。在更新所有物品之后，状态表f在相应的背包容量下存储最佳价值。

本发明的核心理念在于根据余数对容量状态j进行分组，对传统动态规划递归公式进行了改进，减少了求解BKP过程带来的冗余计算，实施例2进一步对改进后的算法进行并行化(即多组同时执行运算)，随着数据量的增大，本发明比现有的算法拥有更好效率，可实现BKP的快速求解。具体而言，本发明将传统DP的计算方式进行了优化，通过维护单调的利润递减列表，具有相同索引余数的每个状态仅可以用O(1)的时间进行计算，因为潜在的更新决策元素包括并删除了每个包含项的一次。因此，FBKP的时间复杂度达到O(NC)的平均值，空间需求达到O(C+N+C/W

现分别将K

表1为随着K

表2为随着N

表3为随着W

表4为FBKP、FBKP parallel和传统DP、MTB2方法解决0-1KP的运行时间对比：

显然，上述实施例仅仅是为清楚地说明本发明的技术方案所作的举例，而并非是对本发明的实施方式的限定。对于所属领域的普通技术人员来说，在上述说明的基础上还可以做出其它不同形式的变化或变动。这里无需也无法对所有的实施方式予以穷举。凡在本发明的精神和原则之内所作的任何修改、等同替换和改进等，均应包含在本发明权利要求的保护范围之内。