Machine World | Math World

记录实验过程

【算法设计与分析】一个经典的问题-0/1背包问题

【背景】

    背包问题(Knapsack problem)是一种组合优化的NP完全问题。问题可以描述为:给定一组物品,每种物品都有自己的重量和价格,在限定的总重量内,我们如何选择,才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。相似问题经常出现在商业、组合数学,计算复杂性理论、密码学和应用数学等领域中。也可以将背包问题描述为决定性问题,即在总重量不超过W的前提下,总价值是否能达到V?它是在1978年由Merkle和Hellman提出的。

【一个例子引出的几种解法】

    在课堂上Boss为我们总结了用动态规划法、回溯法、分支界限法对其进行求解的方法。现将作业贴出供日后参考。

【例子】

已知\( n = 4, C =7, w = (3, 5, 2, 1), p = (9, 10, 7, 4)\),其中:

n 表示为物品数

C 表示背包容量

w 表示物品重量

p 表示物品价值

求解背包装入物品最大价值。

【动态规划法求解】

前文已经介绍了动态规划的一般构成法,现将动态规划步骤重新列举出。

最优解性质分析:

    设\( V(i, j)\)表示前\( i(1 \leq i \leq n)\)个物品装入容量为\( 0 \leq j \leq C \)的背包获得的最大价值,在决策\( x_i \)时,已经确定了\( (x_i, \dots , x_i-1)\)的决策结果,则此时问题可以归纳为下列两种状态:

1、背包容量不足以装入物品 \( i \Rightarrow x_i = 0\)

2、背包可以容纳(装入)物品\( i \Rightarrow x_i = 1\)

递归划分子问题,递归定义最优解

对上一步骤中状态2进行分析:

如果把\( i \)装入背包内,其决策价值等于把前\( i -1 \)个物品装入容量为\( j – w\)背包的价值 + 第 \( i \)个物品的价值,数学表示如下:

\( V_i = v(i-1, j – w_i) + v_i\)

如果\( i\)未装入背包内,则背包在这一决策阶段的价值保持不变,数学表达如下:

\( V_i = v(i-1, j)\)

取两阶段(子问题)的最优解,其递推式如下:

\( V(i, j) = \begin{cases} v(i-1, j) && j < w \\ max\{v(i-1, j), v(i-1, j-w_i) + v_i\}  && j \geq w \end{cases}\)

自底向上计算最优值(填表):

《【算法设计与分析】一个经典的问题-0/1背包问题》

为确定装入背包的具体物品,从\(V(n, c) \)的值按照如下公式向前递推:

\(x_i = \begin{cases}0 && V(i, j) = V(i-1, j) \\ 1, && V(i,j) > V(i-1, j)\end{cases} \)

如图所示:

《【算法设计与分析】一个经典的问题-0/1背包问题》

故使用动态规划法对该问题的求解结果为:\( \{x_1, x_2, x_4\}\)

【回溯法求解】

分析其解空间:

根据需求,对于n=4时的背包问题,其解空间可以用一颗完全二叉树进行表述,如下图所示:

《【算法设计与分析】一个经典的问题-0/1背包问题》

其搜索过程约束条件如下:

\( \sum W_iX_i \leq M(i = 0, \dots, n), W_i > 0, X_i \in [0,1](1 \leq i \leq n)\)

搜索过程中的目标最大值表示如下:

\(\max \sum P_iX_i(i=0, \dots , n-1), P_i > 0, X_i = 0 or 1(0 \leq i \leq n)\)

用语言表示为:在搜索解空间树时,只要左儿子是一个可行节点,搜索就进入左子树,在右子树有可能包含最优解时才进入右子树,否则将右子树剪去。其搜索过程如下图所示:

《【算法设计与分析】一个经典的问题-0/1背包问题》

观察搜索结果,其可行解有:

(1,0,1,1)(1,0,1,0)(1,0,0,1)(1,0,0,0)(0,1,0,1)(0,1,0,0)(0,0,1,1)(0,0,1,0)(0,0,0,1)(0,0,0,0)

最优解为:L=(1,0,1,1),价值为:20

【分支界限法】

使用FIFO队列分支限界法对其求解过程如下:

解空间:

{(0,0,0,0), (0,0,0,1) … (1,1,1,1)}

解空间树:

《【算法设计与分析】一个经典的问题-0/1背包问题》

BFS搜索(FIFO队列)

《【算法设计与分析】一个经典的问题-0/1背包问题》

根据表格可知:

最优解为(1, 0 ,1 ,1)价值为20

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注