基于集合求解01背包问题的跳跃点法
2019-07-12王金燕
文/王金燕
1 引言
01背包问题的具体描述为：有n个物品，物品i（i=1,2,...,n）的重量为wi，价值为vi，一个背包容量为c。要求从背包的价值出发，做出最优的装包决策。与背包问题不同，此处的物品不允许划分，即选择装入一个物品就必须装入其全部。这种01整数的规划决策问题在当前生活中得到了广泛的应用，类似问题已经推广到密码学、商业资金管理、数学应用计算等多个领域。虽然01背包问题的思想很好理解，但由于其NP复杂性，采用一般的算法很难解决。而动态规划算法可以通分析，将原问题逐层划分为若干小问题，通过层层递归得到原问题的解。
2 传统的动态规划求解策略
对于最终背包所包含的物品，可以形象化的用一个n元01向量(x1, x2, ...xn)表示，其中xi=0表示最优装包策略不包含第i个物品，xi=1表示最优装包策略包含第i个物品。则01背包问题则可以抽象为如下数学表达式：
记m(i,j)为一个子问题的最优值。该子问题为：为一个容量为j的背包做决策，选择第i,i+1,...n个物品中装入哪些物品。根据最优子结构性质，子问题的递归式可以表示为：
显然，求解m[][]只需遍历每个物品，时间复杂度为O(c*n),但是当背包容量很大如c>2n时，计算m[][]需要计算时间。
3 改进的跳跃点法求解01背包问题
3.1 算法的提出
很显然，随着背包容量的增加，允许装入背包中的物品有更多的选择余地，则背包的总价值或者保持不变（不再装入新的物品），或者阶梯状上升（选择新的物品装入），不可能出现背包价值减小的情况。即m(i,j)是一个关于j的单调不减函数。
举例来说，当n=5，c=10时，假设w={2,2,6,5,4}，v={6,3,5,4,6}
则m(4,j)，m(5,j)的函数图像如图1所示。
由于背包的容量存在增加时，背包总价值m(i, j)才会发生改变。即m(i,j)不是随着j的连续取值而变化的。此外因为物品不可分割，而单个物品的价值往往是大于1的整数，则m(i, j)也并不是连续增加的值，每装入一个重量为wi的物品，m(i, j)值会跳跃增加相应vi。则将(wi,vi)称为函数m(i, j)的跳跃点。在m(i, j)的计算中，无需再对其子问题保存的值进行比较和赋值，只需要逐层计算跳跃点，最终的跳跃点即包含了背包的最大价值。
3.2 算法说明
此处假定变量j取连续值，求解过程中每求得一个跳跃点就将其插入到一个set集合中，最终该集合是m(i,j)的全部跳跃点集合，记为p[i].对于任意容量为j的背包（即任一个子问题），建立迭代遍历跳跃点集p[i]即可确定m(i, j)的值。前面我们已经说明过m(i, j)的非递减性，所以任一个子问题中的全部跳跃点都是呈阶梯状上升的。
根据递归表达式可知，m(i,j)的跳跃点主要包括以下两类：
①m(i+1,j)的跳跃点集p[i+1];
②m(i+1,j-wi)+vi的跳跃点集q[i+1];
即p[i]=p[i+1]∪q[i+1].
需要注意的是，在所有的跳跃点集中并不全都是正确的跳跃点。下面进行例证：
设(i1, j1)和(i2, j2)都是p[i]中的跳跃点。假设存在一种可能，使得i1≤i2且j2≤j1，说明当背包容量时增加，所包含物品的总价值减少。与前文所述显然矛盾，即(i2, j2)不是真正的跳跃点。(i2, j2) 受控于(i1, j1)，被称为受控跳跃点。实际上，受控跳跃点的出现是由于递归表达式产生的。当m(i,j)=max {m(i+1,j),m(i+1, j-wi)+vi}时，两者中相对较小的点并没有被采用，但却也包含在跳跃点集中，就成为了受控跳跃点。
③由于受控跳跃点是不正确的跳跃点，p[i]=p[i]-{受控条约点}
3.3 算法实现
（1）变量及操作的定义：
定义跳跃点为结构体变量struct point{int x;int y;}；定义一系列set集合p[i]，q[i]表示全部跳跃点集set
q[i+1]为子问题m(i+1,j-wi)+vi的跳跃点集。
图1：m(4，j)m(5，j) 图像
（2）初始化并加入所有可能的跳跃点：
（3）用迭代器遍历每个跳跃点集，删除受控跳跃点。
（4）重复①-③，直到确定p[1]的跳跃点集，该集合中最后一个跳跃点即为所求的背包最大价值。至此算法结束。
4 算法复杂度分析
上述算法的主要计算量在于步骤②-③中的遍历过程。对p[i]集合的合并求解需要遍历每个p[i]保存的跳跃点集,判断并删除删除跳跃点集中的受控跳跃点也需要遍历p[i]，即需要O(|p[i+1]|)的计算时间。而每个跳跃点相应于一个解变量xn序列的01赋值。故p[i]中的元素数目存在上限2n-i+1。从而算法计算跳跃点集所花费的时间为：
5 结语
本文从传统的动态规划求解01背包问题出发，根据递归表达式研究跳跃点法对于问题的求解，同时提出用STL模板库中的set集合存储求解过程中的跳跃点集，避免了重复跳跃点的出现，降低了算法的时间复杂度和空间复杂度。
