求解0-1背包问题的融合贪心策略的回溯算法

j

j

j

j

i

n

i

x

i

C

C

i

14.else

15.break;

i

n

x

i

v

i

i

x

i

19.return maxvalue

O

n

O

n

O

n

n

O

n

n

1.3 0-1背包问题的经典回溯算法

与贪心算法相比，经典回溯算法更看重问题的整体性分析。经典回溯算法是使用深度优先遍历求解0-1背包问题的经典算法。在问题求解的过程中，回溯算法将物品的选择状态构造成一个解空间树，通过遍历解空间树中的每个节点来寻找问题的可行解和最优解。具体地说，经典的回溯算法从解空间树的根节点出发，依次判断解空间树的每一个节点，并选择当前状态下满足问题约束条件的节点，当遍历到叶子节点时，算法对当前各个节点的选择状态进行记录和判断，当约束条件不满足时，回退一步至上一状态或回退多步，直至遍历过解空间树的每一个节点并回溯到根。在搜索的过程中，回溯算法会不断判断是否存在更优的解，并记录和更新目前已找到的最优解。

经典回溯算法解决0-1背包问题的主要步骤如下：

(1)构造问题的解空间树；

(2)确定问题的约束条件。一个是放入背包的物品总重量不超过背包的容量，另一个是放入背包的物品是否构成问题的最优解；

(3)从根节点开始，深度优先遍历解空间树，在遍历的过程中根据问题的约束条件选择性地进行回溯和继续遍历。

O

1.3.1 递归回溯算法

存在两种实现经典回溯的算法，一个是递归算法，一个是非递归算法。递归回溯算法，是指把一个大型的复杂问题分解为一个与原问题相似的、规模较小的问题，通过递归求解小问题并将子问题的解合并，从而得到原问题的解。

算法2给出了递归回溯算法(knap1)的伪代码描述，该算法从位于解空间树根节点的第1个物品开始遍历，依次考虑当前选中物品不放入背包和放入背包时，所有物品的选择状态。当遍历到叶子节点时，进行最优解的约束条件检验并判断是否进行回溯，算法的主要步骤如下：

(1)引入cw和cv分别表示当前状态下背包内物品的总重量和总价值；

(2)对于每一个物品，首先选择“不装入背包”并进行递归，而在进行“装入背包”的选择前，则需要判断所有选中物品的总重量是否满足背包的容量；

(3)当遍历到最后一个物品时，计算此时背包内物品的总价值，判断是否为问题的最优解。

算法2：递归回溯算法knap1。

Initialize maxvalue, cw, cv as 0

knap1(1)

output maxvalue

intknap1(int i)

if i=n+1 then

if cv>maxvalue then

maxvalue←cv;

result←x;

else

x[i]←0;

knap1(i+1);

if cw+w[i]≤C then

x[i]←1;

cv←cv+v[i], cw←cw+w[i];

knap1(i+1);

x[i]←0;

cv←cv-v[i], cw←cw-w[i];

returnmaxvalue

1.3.2 非递归回溯算法

与递归回溯算法不同，非递归回溯算法利用物品的状态值判断是否需要回溯，而不需要借助操作系统提供的递归机制，因而一般具有较高的时空效率。

算法3给出了非递归回溯算法(knap2)的伪代码描述，在该算法中，选中物品在进行“装入”或“不装入”背包的选择前，其状态值首先会被赋值为-1(代码第2行)；当物品的选择状态确定后，其状态值则为0或1(代码第4、15行)；一旦该物品的状态值增加至2时，则需要进行回溯(代码第17、18行)。

算法3：非递归回溯算法knap2。

i

x

i

i

x

i

x

i

i

n

j

n

x

j

w

j

x

j

v

j

10.if cw≤C and cv>maxvalue then

11.maxvalue←cv;

12.result←x;

13.cw←0, cv←0;

14.else

i

x

i

17.else

i

19.end

20.return maxvalue

2 融合贪心策略和剪枝策略的回溯算法

2.1 问题分析

使用贪心算法求解0-1背包问题时，算法从问题的某一初始解出发，选择当前条件下的最优解，并试图构造或逼近问题的整体最优解。贪心算法每一步的决策仅考虑当前的局部信息，其解空间不可回溯再现，具有较强的随机性和不可预知性。这种基于经验或直觉的判断，并不一定能够保证找到问题真正的最优解，在绝大多数情况下，贪心算法得到的解只是问题的近似最优解。但是，由于贪心算法采用局部最优决策，因而往往具有较高的效率。

回溯算法的思想和枚举法类似，即通过尝试问题所有可能的解来寻找问题的最优解，这种算法虽然确保了解的正确性，但是以牺牲算法运行时间为代价。当问题规模较大时，回溯算法的运行时间呈指数式增长，在短时间内可能无法得到问题的最优解。

针对上述特征，该文将贪心算法的高效性和回溯算法的最优性相结合，提出了一种融合贪心策略和剪枝策略的新型回溯算法，简称新型算法。考虑到贪心算法得到的解虽然可能不是问题的最优解，但至少一定是问题的近似解，故将其作为初始解应用于回溯算法，从而可以尽快实现剪枝操作，进而提高回溯算法效率。

因此，新型算法将贪心算法的解作为回溯算法中剪枝策略的判断条件，同时优化了遍历过程中的约束条件，从而在确保得到问题最优解的同时，可以进一步提高算法效率。

2.2 新型算法

算法4给出了所提出的新型算法的伪代码描述。该算法使用递归方法求解0-1背包问题，与经典的回溯算法不同，首先，算法4增加了基于价值的剪枝策略，若背包内物品的总价值与未遍历到的物品的总价值之和小于算法1得到的解，则进行剪枝并回溯。其次，在遍历的过程中，算法4优化了物品选择的约束条件，将经典回溯算法的约束条件“放入背包的物品总重量不超过背包的容量”修改为“当前选中的物品重量满足背包的剩余容量”。

所提出新型算法的主要步骤如下：

i

(2)算法1得到的解存储到maxvalue_greedy中；

i

C

(4)首先判断选中物品“不装入背包”时是否需要剪枝；

(5)若选中物品“装入背包”，首先判断物品重量是否满足背包的剩余容量，若“能装入”，则继续进行步骤4的剪枝判断，最终确定物品的选择状态。

算法4：新型算法。

C

i

2.maxvalue_greedy←greedy()

C

4.output maxvalue

i

i

n

i

n

v

i

x

i

4.if value>maxvalue then

5.maxvalue←value;

6.result←x;

7.else

v

i

i

v

i

w

i

11.if pv+rv>maxvalue_greedy then

x

i

i

i

w

i

v

i

v

i

x

i

15.return maxvalue

在新型算法中，递归函数GB(第3行)的含义是：若当前考虑的物品“不装入背包”，计算此时背包内物品的总价值与未遍历到的物品的总价值之和，若大于maxvalue_greedy，则表明，在当前物品的选择状态下，存在将某些物品装入背包后使得总价值提高的可能，因此进行递归；否则，表明在当前物品的选择状态下，任何后续的装入选择都将不可能超过现在背包内物品的总价值，此时则进行剪枝并回溯。若当前选中物品想要“装入背包”，首先判断该物品的重量是否满足背包的剩余容量，然后继续判断是否“有必要装入”。当遍历到最后一个物品时，计算此时背包内物品的总价值并判断是否为问题的最优解。

新型算法的核心思想是：对于每一个物品，只有该物品“能装入背包”且“有必要装入”，才会将其放入背包中。

3 仿真实验与分析

3.1 实验环境

该文进行了大量的仿真实验，具体实验环境为：CPU：i7-8550U，内存：DDR2 16 GB；硬盘：1 TB；缓存，8 MB；PF使用率：36%～45%；编程语言：Java，软件开发工具：Eclipse。分别实现了递归回溯算法(算法2)、非递归回溯算法(算法3)和新型算法(算法4)，并在不同问题规模下进行仿真实验与分析。

n

f

f

f

3.2 实验结果分析

f

n

表1 三种算法在实验系数f=0.3的时间耗费

表2 三种算法在实验系数f=0.6的时间耗费

表3 三种算法在实验系数f=0.8的时间耗费

通过上述比较，可以得出以下结论：

(1)在不同实验系数下，随着问题规模的增加，所有算法的时间耗费都呈现上升趋势，其中经典的递归回溯算法和非递归回溯算法的上升趋势更为显著。结合算法的时间复杂度可知，经典回溯算法的时间耗费随着问题规模的增加呈指数级增长。此外发现，非递归回溯算法较递归回溯算法具有较高的运行时间。

(2)在同一实验系数、同一问题规模下，与经典回溯算法相比，该文所提出的新型算法在保证得到问题的最优解的同时，具有较小的时间耗费，特别是在问题规模较大时，效果更为明显。

在不同实验系数下，对递归回溯算法(算法2)和非递归回溯算法(算法3)的时间耗费进行了对比，从而验证实验系数是否对经典回溯算法的执行时间产生影响。实验结果见表4。

表4 经典回溯算法在问题规模n=20时的时间耗费

根据表4可知，当实验系数从0.3逐渐增加至0.9时，递归回溯算法的时间耗费线性增长至某一数值后，在该数值处呈现小幅度波动；非递归回溯算法的时间耗费则始终在某数值处小幅度波动。

f

图1 新型算法的时间耗费(f=0.8)

从图1可以看出，在实验系数为0.8时，只有当问题规模近似增加至70时，新型算法的时间耗费才会有较为明显的递增，效率远远高于经典回溯算法。

表5列出了在不同的实验系数和不同的问题规模下，新型算法得到问题最优解的时间耗费情况。从表5中可知，新型算法普遍随实验系数的增加而减少，其原因在于，随着实验系数的增加，背包的容量不断增大，背包可以容纳的物品数量相应增加，从而减少了回溯的概率，进而提高了算法效率。

表5 新型算法在不同实验系数、不同问题规模下的时间耗费

4 结束语

0-1背包问题是经典的NP完全问题，而经典的回溯算法采用枚举的思想，通过深度优先搜索解空间树寻找问题的最优解。在问题规模较小时，回溯算法同其他求解0-1背包问题的经典算法相比，具有更小的时间耗费和空间耗费。但随着问题规模的增加，回溯算法在时间和空间上都有极为明显的增加，这种增加导致算法在较短时间内无法得到问题的最优解。

该文将贪心算法的高效性和经典回溯算法的最优性相结合，提出的融合贪心策略与剪枝策略的新型算法，将经典贪心算法得到的问题近似解用于剪枝策略的判断条件中，减少了经典回溯算法遍历过程中的无效搜索；同时，在进行物品选择的判断时，使用背包剩余容量作为约束条件，大大提高了算法的求解效率。大量仿真实验结果表明，该新型算法在保证得到问题最优解的同时，有效提高了算法的运行效率。