动态规划算法解决背包问题

动态规划算法解决背包问题一、动态规划算法概述动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从子问题解得到原问题解。但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解极值问题时,有些子问题被重复计算了许多次。如果能够保存已解决的子问题的答案,而在需要时再找出已求得的答案,就可以避免大量重复计算,从而得到多项式时间算法。动态规划VS分治法:相同点:基本思想均是将原问题分解成若干个子问题,先求子问题,然后从子问题的解得到原问题的解

一、动态规划算法概述

动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从子问题解得到原问题解。

在这里插入图片描述

但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解极值问题时,有些子问题被重复计算了许多次。

在这里插入图片描述

如果能够保存已解决的子问题的答案,而在需要时再找出已求得的答案,就可以避免大量重复计算,从而得到多项式时间算法。

在这里插入图片描述

动态规划 VS 分治法

  • 相同点:基本思想均是将原问题分解成若干个子问题,先求子问题,然后从子问题的解得到原问题的解;
  • 不同点:
    • 适用于动态规划求解的问题,分解得到的子问题往往不是互相独立的;
    • 动态规划为自底向上,而分治法为自顶向下。

当分解出的子问题不相互独立的话,若使用分治法来求解此类问题,会导致使用指数级的运行时间,而子问题的个数只有多项式量级。所以,此类问题不适合使用分治法。

动态规划是如何减少对重复子问题求解的呢?

答案是保存已求解的子问题的解,在需要时找出,从而避免大量的重复计算得到多项式的运行时间;通常用一个表来记录所有已解决的子问题。

动态规划算法通常用于求解具有某种最优性质的问题

二、背包问题

2.1 什么是背包问题

今年的年会,聪明大方的老板为了激励员工,决定买三种类型的奖品奖励给勤奋的员工小王。

在这里插入图片描述

为了让自己不至于放血太多又不会显得太抠门,美其名曰考验员工小王的智商。机智的老板想到了一个好法子:给小王发一个最大能装下 4 磅物品的背包,只有装到背包中的物品才归属于小王。

如果你是员工小王,怎么装才能得到最大的物品价值呢?

2.2 背包问题思路分析

首先,最容易想到的方法,就是计算出各种可能的奖品组合的情况,找出价值最高的组合放入到背包中。对于三种奖品,共有 8 种的组合,对于四种奖品,共有 16 种组合。每增加一种奖品,需要计算的组合数都将翻倍。如果明年老板决定奖励十一种奖品给小王,那小王最好还是放弃奖品算了。我们可以看到,这种算法的时间复杂度为 O(2ⁿ),效率较低。

如何找到最优解呢?答案是使用动态规划

对于背包问题,可以先解决小背包(子背包)的问题,然后逐步解决原来的问题。

在这里插入图片描述

每个动态规划算法都从一个网格开始,背包问题的网格如下。

在这里插入图片描述

网格的各行为奖品,各列为不同容量(1~4磅)的背包。所有这些列都是必要的,因为它们将用于计算子背包中的物品价值。

第一步:

我们首先假设可选择的奖品只有吉他(1 磅)。当背包的容量为 1 时,刚好放下一个吉他,此时背包价值为 1500。当背包的容量为 2、3、4 时,由于可选的商品只有吉他且同样的奖品只能拿一件,因此即便会使背包的空间浪费,背包中仍然是只能放一个吉他,背包中的价值仍然为 1500。

在这里插入图片描述

第二步:

我们再假设可选的商品只有吉他(1 磅)和音响(4 磅)。当背包的容量为 1、2、3 时,由于音响的重量为 4,因此无法放入到背包中,背包中只能放入一个吉他。

在这里插入图片描述

当背包的容量为 4 时,刚好等于音响的重量。这个时候有两个选择:一是只放入一个吉他;二是只放入一个音响。由于音响的价值为 3000,大于吉他的价值,因此选择将音响放入背包,此时背包中的价值为 3000。

在这里插入图片描述

第三步:

我们在假设可选择商品有吉他(1 磅)、音响(4 磅)、笔记本电脑(3 磅)。当背包的容量为 1、2 时,毫无疑问,背包中只能放一个吉他。此时背包的价值为 1500。

在这里插入图片描述

当背包的容量为 3 时,有两种选择:一是只放入一个吉他;二是只放入一个电脑。由于电脑的价值高于吉他,因此将电脑放入。此时背包的价值为 2000。

在这里插入图片描述

当背包的容量为 4 时,仍然有两种选择:一是放入一个吉他和电脑;二是只放入一个音响。由于吉他和电脑的总价值高于音响的价值,因此将吉他和电脑放入。此时背包的价值为 1500 + 2000 = 3500。

在这里插入图片描述

因此,将吉他和笔记本电脑装入背包时价值最高,这就是小王的最优解。

总结:

那么这个过程,如何用数学公式表达呢?

我们首先约定一共有 N 件物品,第 i 件物品的重量为 w[i],价值为 v[i],背包的承载上限为 W。再约定一个状态 cell[i][j] 表示将前 i 件(这里的前 i 件指的是有 i 件可选)物品装进限重为 j 的背包可以获得的最大价值(0<=i<=N0<=j<=W)。

那么我们可以将 cell[0][0...W] 初始化为 0,表示将前 0 个物品装入书包的最大价值为 0。

i>0 时,cell[i][j] 有两种情况:

  1. 不装入第 i 件物品,则背包最大价值就是相同背包容量下只有 i-1 件物品可选时的最大价值,即 cell[i-1][j]
  2. 装入第 i 件物品(若背包容量够),则最大价值为当前物品价值加背包剩余容量的最大价值,即 v[i] + cell[i-1][j-w[i]]

那么 cell[i][j] 的值,就是这两种情况下的最大值。由此可以得到方程:
c e l l [ i ] [ j ] = m a x { c e l l [ i − 1 ] [ j ] c e l l [ i − 1 ] [ j − w [ i ] ] + v [ i ] j > = w [ i ] cell[i][j] = max \left \{\begin {aligned}&cell[i-1][j]\\&cell[i-1][j-w[i]] + v[i]\end{aligned}\right. \quad\quad j>=w[i] cell[i][j]=max{
cell[i1][j]cell[i1][jw[i]]+v[i]
j>
=w[i]

求得所有的 cell[i][j] 之后,最后一个值就是背包问题的最大值。

2.3 背包问题代码实现

public static void main(String[] args) { 
   
    int[] w = { 
   0, 1, 4, 3};    // 物品的重量
    int[] v = { 
   0, 1500, 3000, 2000};    // 物品的价值

    int num = w.length; // 物品的数量可能的个数 (0~3,共 3 个)
    int weight = 5; // 背包的容量可能的个数 (0~4,共 5 个)

    int[][] cell = new int[num][weight];    // cell[i][j] 表示前i个物品可选,背包容量为j时的最大价值
    int[][] record = new int[num][weight];  // record[i][j] 用于标记第i个物品有没有放入容量为j的背包

    for (int i=1; i<num; i++){ 
     // 遍历物品
        for (int j=1; j<weight; j++){ 
      // 遍历背包容量
            if (w[i]>j){ 
       // 如果当前物品重量大于背包容量
                cell[i][j] = cell[i-1][j];  // 不装入
            }else{ 
     // 如果当前物品重量小于等于背包容量
                int value_1 = cell[i-1][j]; // 不放入第 i 个物品的背包价值
                int value_2 = v[i] + cell[i-1][j-w[i]]; // 放入第 i 个物品后的价值
                /* 把最大价值放入背包 */
                if (value_1 > value_2){ 
   
                    cell[i][j] = value_1;
                }else{ 
   
                    cell[i][j] = value_2;
                    record[i][j] = 1;   // 用于标记在本网格放入了第 i 个物品
                }
            }
        }
    }

    // 最后一个网格就是最大价值
    System.out.println("背包价值为:" + cell[num-1][weight-1]);

    // 由于最后一个网格就是最大价值
    // 因此,逆序遍历 record 找到最后一个放入的物品,然后找到剩余空间价值是放入第几个物品
    int i = record.length-1;
    int j = record[0].length-1;
    while (i > 0 && j > 0){ 
   
        if (record[i][j] == 1){ 
   
            System.out.printf("放入了第 %d 个商品\n", i);
            j = j - w[i];   // 背包剩余容量
        }
        i--;
    }
}

运行结果如下:

在这里插入图片描述
【注】:本文的图大多出自《算法图解》。

今天的文章动态规划算法解决背包问题分享到此就结束了,感谢您的阅读,如果确实帮到您,您可以动动手指转发给其他人。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/24825.html

(0)
编程小号编程小号

相关推荐

发表回复

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