0-1背包问题解题策略

一、0-1背包问题描述

给定n种物品和一个背包。物品i的重量是Wi, 其对应价值为Vi, 背包容量为C, 且物体不可拆分, 那么如何选择装入背包的物品, 使得装入背包中物品的总价值最大?

二、动态规划求解

动态规划的基本思想:将待求解的问题分解成若干个子问题, 自底向上求解子问题。在求解任意一个子问题时, 列出各种可能的局部解, 保留那些有可能达到最优的局部解。依次i解决各个子问题, 最后一个子问题就是初始问题的解。适用动态规划求解的问题: (1) 最优子结构:问题最优解所包含的子问题的解也是最优的。 (2) 无后效性:某状态以后的过程不会影响以前的状态, 只与当前状态有关。 (3) 重叠子问题:子问题直之间不是独立的, 一个子问题在下一个阶段的决策中可能被多次使用到。解题分析过程如下:

(1) 划分阶段:决定每个物品放不放为一个阶段, 题中共有7件物品, 所以有7个阶段。

(2) 递归定义最优解:背包最大容量C, 背包容量为c, 第i件物品的重量为W[i], 价值为V[i], 设n件物品放在容量为c的背包里的最大价值为M (n, c) 则:M (n, c) =MAX (M (n-1, c) , M (n-1, c-W[i]) +V[i]) c<=C; (3) 边界条件:M (0, c) =0; (4) 备忘录自上而下计算M (7, 150) ; (5) 得到最优值, 计算最优解;

(6) 核心代码:

三、回溯法求解

回溯法是一个类似枚举的搜索过程, 在搜索的过程中寻找问题的解, 当不满足求解条件时, 就回溯返回尝试新的路径。回溯方法的基本思想:在包含问题的所有解的解空间树中, 按照深度优先的策略从根节点搜索解空间树。当搜索到某一结点时, 要先判断该节点是否包含问题的解, 如果包含就从该节点继续往下搜索, 否则逐层向其祖先节点回溯。回溯法的一般解题步骤: (1) 针对所给问题, 确定问题的解空间。 (2) 确定易于搜索的解空间结构。 (3) 以深度优先方式搜索解空间, 并在搜索过程中用剪枝函数来避免无效搜索。解题分析过程如下:

解空间是一个一维向量, 可以用X[n]表示, X[i]的取值为0或1。 (2) 0-1背包问题解空间树是子集树。 (3) 剪枝函数: (1) 约束条件:∑W[i]*X[i]<=C; (2) 限界函数:当前背包中的价值cv+剩余物品总价值>=当前最优价值bestv。

核心代码:

四、分支限界法求解

分支限界:广度优先搜索+剪枝优化。 (1) 将根节点加入队列。 (2) 从队列中取出首节点, 使其成为扩展节点, 一次性生成他的所有孩子节点, 舍弃那些不可能导致可行解或是最优解的孩子节点, 其余的节点则进队列。 (3) 重复上述扩展过程, 直到找到问题的解或者队列为空时止。分支限界的一般解题步骤和0-1背包问题的解题分析过程同回溯法类似, 树的遍历方式不同, 如果选用优先队列分支限界法, 必须确定优先级。核心代码如下:

五、三种求解策略比较

三种算法各有各的特点, 回溯法在空间复杂度上要低些, 它占用的内存是解空间的最大长度, 而分支限界所占用内存是解空间的大小。动态规划在时间复杂度和空间复杂度方面相对折衷, 一般使用动态规划解决0-1背包问题。

尽管求解0-1背包问题的算法有很多种, 但问题规模过大时, 这些算法在时间货空间上的复杂度还是相当大的, 应用起来还存在一定的局限性。我们需要对算法进行不断的改进和完善。

摘要：背包问题是一种组合优化的NP完全问题, 相似问题经常出现在商业、组合数学、计算复杂性理论、密码学和应用数学等领域中。背包问题已经研究了一个多世纪, 是非常经典的问题之一, 拥有多种解题策略。

关键词：背包问题,动态规划,回溯法,分支限界法,时间复杂度

参考文献

[1] 王熙照, 贺毅招.求解背包问题的演化算法[J].软件学报, 2017, vol.28lssue (1) :1-16.

[2] 蓝雯飞, 吴子莹, 杨波.背包问题的动态规划改进算法[J].中国民族大学学报, 2016, 35 (4) :101-105.

[3] 田秀芹.求解0-1背包问题算法研究[J].现代经济信息, 2017 (07) :386-388.