对01背包,完全背包的一些理解

红太狼 2022-09-07 04:54 35阅读 0赞

**动规理解：**  
动规就是利用前面已知的来推到后面未知的算法。  
除了一开始直接初始化的值，后面的每个值都通过前面已知的值，根据某些公式推导出。

而01背包问题，就是有n件物品，没件都有重量和价值，将其装到一个有容量的背包，问最大价值能装多少？  
**递归公式：dp\[i\]\[j\]=max(dp\[i-1\]\[j\],dp\[i-1\]\[j-value\[i\]\]+value\[i\]);  
i代表物品，j代表背包容量；dp\[i\]\[j\]代表将\[0-i\]件物品放到容量为j的背包最大可以获取多少价值？**

从表达式可以看出，每个dp\[i\]\[j\]都从他的上一层，也就是i-1层推出。  
因为物品价值一般都是大于0的，所以只要初始化i=0的那一层（也就是第一件物品），后续的都可以根据前面已知的得出答案。

滚动数组可以让数组从二维降到一维，也就是当前层是当前i层的值和上一层i-1的值共存，当当前层遍历完毕，当前层的所有值都会把一维数组上一层的值全部覆盖掉。

**01背包问题下滚动数组，为什么要先遍历物品再遍历容量？**  
因为本质上，滚动数组和原来二维的是差不多的，计算某一个值是通过上一层结果得出的，可能需要使用到上一层，也就是i-1层的下标比当前下标j小的任何数。  
先遍历物品，就是先把i-1层计算出来，符合要求。  
而先遍历背包容量，先计算出的数组，每次循环只有一个i-1层的数据，并且每一层都会把上一个覆盖掉，但是实际计算需要的是一整层的数据，因为都可能会用到。

**为什么二维的时候先便利物品或者先遍历容量都可以？**  
因为二维的时候不会出现数据覆盖，计算后面的时候，前面的值都保存起来了，可以直接使用。

**01背包问题下滚动数组，为什么第二层循环（遍历背包容量）要从后往前遍历？**  
因为滚动数组的计算本质上和二维的时候的计算差不多，不过二维的时候没有覆盖，一维的时候，如果先计算前面的，再计算后面的，后面的计算的时候，需要使用上一层的数据（只会使用下标比自己小的），而前面已经把上一层的数据都覆盖了，无法获取到上一层的值，因此不能从前往后遍历。  
而从后往前遍历，计算下标大的值的时候，下标小的上一层值未被覆盖，可以使用，这样就不会出现上面不可用的问题了。

完全背包，就是物品数量无限。然后求满足条件的xx最小，最少，xx最多，最大。  
**完全背包的两次循环，遍历背包容量的一层应该从0开始，因为每件物品都有无数件，同一层需要重复将某个值加入。**

如果求的是达成某某条件的方法有多少种？就需要分排列和组合两种。  
**如果是组合，就要求先遍历物品，再遍历背包容量；  
如果是排列，就要求先遍历背包容量，再遍历物品。  
并且求方法数(含组合数，排列数)的滚动数组方式的递推公式一般是:dp\[j\]+=dp\[j-nums\[i\]\];  
也就是选择nums\[i\]的方法数+不选择nums\[i\]的方法数得到考虑nums\[i\]的方法数**