背包问题总结

2024-01-09 23:45:28

1.背包问题是什么?有哪些?

背包问题包含:0-1背包、完全背包、多重背包,还有一些特殊的如:分组背包、混合背包

? ? ? ? 0-1背包:多种物品,每个物品1个

? ? ? ? 完全背包:多种物品,每个物品n个

? ? ? ? 多重背包:多种物品,每个物品不一样多个

最基础的是:0-1背包、完全背包

竞赛类:分组背包、混合背包

(多重背包在Leetcode不多见,其他比较复杂的情况,多是由0-1背包进化而来)

最存粹的背包问题(0-1背包问题)一般是:

? ? ? ? 给出诸多物品,每个物品有价值和重量两个属性,此时有一个最多载重m的背包,问如何装包,可以使包里的物体价值最高。

2.背包问题的思路

首先明确,背包问题属于动态规划问题。

其次,按照动态规划的一般步骤

  1. 明确dp数组及下标的含义。
  2. 确定递推公式,但是递推公式只是动态规划的一部分,而非全部
  3. dp数组初始化
  4. 确定遍历顺序:从前往后?从后往前?
  5. 打印dp数组, 用于debug验证等。

3.背包问题易理解的解题过程

(1)二维dp数组解题

? ? ? ? a.二维数组dp[i][j]的含义是:编号在[0,i]之间的物品任取,放入容量为j的背包时,能获得的最大价值。

? ? ? ? i的取值[0-n-1]是n个物品的编号

? ? ? ? j的取值是[0,m]是背包容量从0到m的递进。

? ? ? ? b.递推公式:

? ? ? ? 如下图所示:dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i]]+values[i])

? ? ? ? c.?如何进行初始化呢?

? ? ? ? 其值总是从上面和左面推导而来,总是初始化第一列和第一行。

? ? ? ? 其余的值,初始化为-1,以区别价值为0的情况。

? ? ? ? d.如何进行遍历呢?

? ? ? ? 因为既要遍历各个物品,又要遍历各个大小的背包,所以我们需要两个嵌套for循环。

? ? ? ? 一个for循环遍历物品,一个for循环遍历背包。

? ? ? ? 先遍历物品再遍历背包,还是先遍历背包再遍历物品呢?

? ? ? ? 由于dp数组是二维的,保留了各个背包及物品维度的所有信息,先便利哪个都可以。

????????

//先物体再背包:按行填充dp数组
for(int i:物品){
    for(int j:背包){
        dp[i][j]=Max(dp[i-1][j],dp[i-1][j-weight]+values[i])
    }
}

//先背包再物体:按列填充dp数组
for(int j:背包){
    for(int i:物品){
        dp[i][j]=Max(dp[i-1][j],dp[i-1][j-weight]+values[i])
    }
}

4.背包问题的存储压缩思路

一维dp数组解题:动态滚动数组

? ? ? ? a.一维数组dp[j]的含义是:n个物品任取,放入容量为j的背包时,能获得的最大价值。

? ? ? ? j的取值是[0,m]是背包容量从0到m的递进。

? ? ? ? b.递推公式

? ? ? ? 一维动态滚动数组,是基于二维数组的存储压缩的改进版本。

????????dp[j]=max(dp[j],dp[j-weight[i]]+values[i])

? ? ? ? c.初始化

? ? ? ? dp数组总是由最左边推导而来,故对最左边的数据进行初始化,右边的数据要么和左边一样,要么比左边大,所以可以初始化为左边值得大小,故所有值初始化为0.

? ? ? ? 二维dp数组的行信息进行不断的更新。把dp[i=1]行的数据拷贝到dp[i]行,然后对数据进行更改。

? ? ? ? d.遍历顺序

? ? ? ? 在二维dp数组中,按照行填充还是按照列填充,最终都能得到完整得dp数组。

? ? ? ? 但在一维数组中,本质上是原二维数组得滚动行变换过程,其本质上固定了按行遍历的要求。

? ? ? ? 所以我们应该按行填充,两个for循环,先遍历物品,后遍历背包。

?????????e.注意:物品重复放入问题

? ? ? ? 在先物品后背包的过程中,顺序遍历背包大小,会导致物品重复装入的问题。

? ? ? ? 故考虑倒序遍历背包大小,来保证每个物品只装入一次。? ?

? ? ? ? 为什么倒序能解决这个问题?? ??

? ? ? ? 对于二维数组来说,每一层是隔离的。

? ? ? ? 但对于一维数组来说做不到这一点。从前往后处理背包大小问题,就会导致,我们使用该层更新过的值,对本行后面的值做操作,从二维递归公式来看,这是不对的。

? ? ? ? 我们需要这个位置之前的、尚未更改过的值,来推导后面的值。

? ? ? ? 又因为,我们总是从左边的值,推右边的值;所以就从最后一个值开始更新,来保证之前的值还是原来未操作过的状态,即i-1行的状态。

5.拔高的点

? ? ? ? 准确理解两种动态规划过程中遍历顺序的选择,及原因。

文章来源:https://blog.csdn.net/lt_BeiMo/article/details/135489551
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。