0/1背包问题——动态规划、回溯、分支限界法对比

目录

  • 1.问题描述
    1.1 问题描述
    1.2 问题的数学表示（规划类问题，此种表示可以转换为回溯法）
    1.3 三种方法的比较
  • 2.动态规划
    2.1 刻画一个最优解的结构特征（最优子结构）
    2.2 递归地定义最优解的值（重叠子问题）
    2.3 计算最优解的值，通常采用自底向上的方法
    2.4 利用计算出的信息构造一个最优解
  • 3.回溯法
    3.1 01背包问题的数学描述
    3.2 用回溯法搜索解空间
    3.3 一个示例
  • 4.分支限界法
    4.1 分支限界法解决0-1背包问题
    4.2 一个示例
  • 5.可以转换为0-1背包问题的双核问题
    5.1 题目描述
    5.2 转化为背包问题

    • 1.问题描述

    1.1 问题描述

    假定n个商品重量分别为w 0 , w 1 , ..., w n-1 ，价值分别为p 0 , p 1 , ..., p n-1 ，背包载重量为M。怎样选择商品组合，使得价值最高？

    1.2 问题的数学表示（规划类问题，此种表示可以转换为回溯法）

  • 假设x i 表示商品i被装入背包的情况，x i = 0,1。根据题目要求，有如下约束方程和目标函数：
  • 动态规划通过最优子结构，将问题转换为子问题的求解。转换的过程中，涉及到某个具体的商品是否选择的问题。
  • 回溯法根据数学表达式，搜索解向量(x 1 , x 2 , ..., x n )的整个解空间
    搜索的时候利用贪心性质（按照单位重量价值递减排序，估算可能的最高上界）、以及已经计算出的可行解作为界限进行剪枝。
    但是回溯法，原则上要穷尽所有可能，只不过是对有些分支提前返回了。
  • 分支限界法
    剪枝方法同回溯法是一样的：利用贪心性质（按照单位重量价值递减排序，估算可能的最高上界）、以及已经计算出的可行解作为界限进行剪枝。
    唯一的不同是，分支限界法利用的是优先队列，并且，当针对一个结点进行扩展时，会将所有儿子结点进行展开，计算出所有儿子结点所能达到的最高上界。因此，当一个优先队列中首结点是一个可行解，则结束。
  • 因此，可以看出回溯法与分支限界法的本质不同是在于搜索解空间的遍历方式不同。
    回溯法是深度优先，要穷尽解空间的所有可能，找到最优解。
    分支限界法是广度优先，本质上也是穷尽了解空间的所有可能，找到最优解。

    2.动态规划

    2.1 刻画一个最优解的结构特征（最优子结构）

  • 假设01背包问题的一个最优解为S，其中i为序号最大的商品；
    那么S' = S - {i}必然是M - w i 的最优解
    证明方法可以采用cut-paste方法进行证明

    • 2.2 递归地定义最优解的值（重叠子问题）

  • 定义c[i, w]为商品1,....,i，最大重量为w的最优解（最大价值）。那么就有以下两种情况：
  • 如果w i > w，c[i, w]转化为求解一个子问题c[i-1, w]；
  • 如果w i ≤ w，c[i, w]转换成了求解两个子问题：
    一个包含商品i，p i + c[i-1, w- w i ]；
    一个不包含商品i，c[i-1, w]；
    两种情况中的较大者即为c[i, w]
  • （重叠子问题）很显然c[i-1, w-w i ]与c[i-1, w]有重叠子问题。
  • 上界bound = 0
  • 假定第i层左儿子表示商品i被装入背包，右儿子表示未被装入背包
  • 将物体按照价值重量比的非增顺序排序，然后按照这个顺序搜索，在搜索过程中，尽量沿着左儿子继续前进。
  • 当不能沿着左儿子继续前进时，得到问题的一个部分解，并把搜索转移到右子树。此时，估计由这个部分解所能得到的最大价值，把该值与当前的上界进行比较，如果高于上界，就继续在右子树上搜索，知道找到一个可行解，用可行解的值刷新上界bound。
  • 向上回溯，寻找其他可行解。如果部分解所估计的最大值小于当前的上界，就丢弃当前正在搜索的部分解，直接向上回溯。

    • 最大值的估算法（跟分支限界法本质上是一样的）

  • 假定当前解是{x 0 , x 1 , ..., x k-1 }
  • 如果当前的结点是左儿子分支结点，就转而搜索相应的右儿子分支结点；
  • 如果当前的结点是右儿子分支结点，就沿着右儿子分支结点向上回溯，知道左儿子分支结点为止，然后再转而搜索相应的右儿子分支结点

    • 3.2.3 回溯法的步骤描述

    w_cur——表示当前正在搜索的部分解中转入的总重量
    p_cur——当前总价值
    p_est——部分解可能达到的最大价值的估计值
    p_total——当前搜索到的所有可行解中的最大价值，是当前目标函数的上界
    y k 、x k ——部分解的第k个分量及其副本
    k——表示当前搜索深度

  • step1.按商品价值重量比的非增排序排序
  • step2.w_cur、p_cur和p_total初始化为0，把部分解初始化为空，k=0
  • step3.从当前的部分解可取得的最大价值p_est
  • step4.若p_est > p_total，转step5；否则，转step8
  • step5.从v k 开始把商品装入背包，直到没有商品可装货装不下v i 为止，并生成部分解y k , ..., y i ，k ≤ i < n，刷新p_cur
  • step6.如果i ≥ n，得到一个新的可行解，把所有的y i 复制给x i ，p_total = p_cur，p_total是目标函数的新界；令k = n，转step3，以便回溯搜索其他的可能解
  • step7.否则，得到一个部分解，令k=i+1，舍弃商品v i ，从商品v i+1 继续装入，转step3.
  • （ 回溯 ）step8.当i ≥ 0且y i 为0时，执行i = i -1，直到y i ≠ 0为止；即沿右儿子分支结点方向回溯，直到左儿子分支结点。
  • step9.如果i < 0，算法结束，否则，转step10
  • step10.令y i = 0，w_cur = w_cur - w i , p_cur = p_cur - p i , k = i + 1，转step3；从左儿子分支结点转移到相应的右儿子分支结点，继续搜索其他的部分解或可能解。

    • 3.3 一个示例

    M = 50
    商品重量分别为5,15,25,27,30
    商品价值分别为12,30,44,46,50
    上面已经按照单位重量价值递减顺序排列。

    4.1.1 分支方法（二叉分支）

  • 假设比值p i /w i 最大的商品序号为s（s ∈ S 3 ），用s进行分支，一个分支结点表示把商品s装入背包，另一个分支结点表示不把商品s装入背包。
    当商品按照价值重量比递减排序后，s就是集合S 3 (k)中的第一个元素。特别地，当搜索深度为k时，商品s的序号就是集合S中的元素k。
    • 把商品s装入背包的分支结点
    S 1 (k+1) = S 1 (k) ∪ {k}
    S 2 (k+1) = S 2 (k)
    S 3 (k+1) = S 3 (k) - {k} 不把商品s装入背包的分支结点
    S 1 (k+1) = S 1 (k)
    S 2 (k+1) = S 2 (k) ∪ {k}
    S 3 (k+1) = S 3 (k) - {k}

    4.1.2 上界估算方法（按照单位价值最大进行贪心选择）

  • 假定b(k)表示在搜索深度为k时，某个分支结点的背包中商品的价值上界。
    此时S 3 (k) = {k, k+1, ..., n-1}。用如下方法计算两种分支结点背包中商品价值的上界：
  • 上述公式的理解
    1）按照一个商品是否加入到S 1 集合，总共有2 n 个叶子节点，每个叶子节点对应一种情况
    2）当一层一层向下搜索是，如果当前S 1 集合中的总重量超过了载重量M，则直接将b(k)置为0，该分支终止。
    为什么这样做？因为在搜索上一层时，该商品不应该加入到S 1 集合，这种不加入该商品情况对应于另一个分支。加入该商品的此分支已经不满足要求了，所以剪枝。

    4.1.3 分支限界法求解步骤

    每个结点都包含如下信息：
    S 1 ——当前选择装入背包的商品集合
    S 2 ——当前不选择装入背包的商品集合
    S 3 ——当前尚待选择的商品集合
    k——搜索深度
    b——上界
    bound——一个可行解的取值，当做剪枝的标准

  • step1.bound = 0，把商品按价值重量比递减排序
  • step2.建立根节点X
    X.b = 0
    X.k = 0
    X.S 1 = ∅
    X.S 2 = ∅
    X.S 3 = S
  • step3. 若X.k == n，算法结束，X.S 1 即为装入背包中的物体，X.b即为装入背包中物体的最大价值；
    否则转向step4
  • （ 分支1 ）step4.建立结点Y
    Y.S 1 = X.S 1 ∪ {X.k}
    Y.S 2 = X.S 2
    Y.S 3 = X.S 3 - {X.k}
    Y.k = X.k + 1
    计算Y.b，将Y.b与bound进行比较，据此判定是否插入优先队列；当S 3 为空时，找到一个可行解，判定是否更新bound。
  • （ 分支2 ）step5.建立结点Z
    Z.S 1 = X.S 1
    Z.S 2 = X.S 2 ∪ {X.k}
    Z.S 3 = X.S 3 - {X.k}
    Z.k = Z.k + 1
    计算Z.b，将Z.b与bound进行比较，据此判定是否插入优先队列；当S 3 为空时，找到一个可行解，判定是否更新bound。
  • step6.取出优先队列首元素作为结点X，转向step3

    • 4.2 一个示例

    有5个商品，重量分别为8,16,21,17,12，价值分别为8,14,16,11,7，背包的载重量为37，求装入背包的商品及其价值。

    5.1 题目描述

    一种双核CPU的两个核能够同时的处理任务，现在有n个已知数据量的任务需要交给CPU处理，假设已知CPU的每个核1秒可以处理1kb，每个核同时只能处理一项任务。n个任务可以按照任意顺序放入CPU进行处理，现在需要设计一个方案让CPU处理完这批任务所需的时间最少，求这个最小的时间

    输入描述:

    输入包括两行： 第一行为整数n(1 ≤ n ≤ 50) 第二行为n个整数length[i](1024 ≤ length[i] ≤4194304)，表示每个任务的长度为length[i]kb，每个数均为1024的倍数。

    输出描述:

    输出一个整数，表示最少需要处理的时间

    输入例子:

    5 3072 3072 7168 3072 1024

    输出例子:

    5.2 转化为背包问题