01背包
题目
假设山洞里共有a, b ,c, d ,e这5件宝物(不是5种宝物),它们的重量分别是2, 2, 6, 5, 4,它们的价值分别是6, 3, 5, 4, 6, 现在给你个承重为10的背包, 怎么装背包,可以才能带走最多的财富。
分析
dp问题, 先创建dp状态表帮助分析
先形式化题目中的一些数据:
有m件物品,m=5
背包容量c,c=10
w[i], 第i件物品的重量
v[i], 第i件物品的价值
-
状态定义 f[i][j]表式i件物品放入容量为j的背包的价值
-
状态转移方程 当没有物品(i=0)或者背包没有剩余空间(j=0)时f[i][j]=0, f[i][j]是最优解, 那么f[i-1][j-w[i]]必然也是最优解,现在考虑放入第i件物品,
- 不放则价值不变 f[i][j] = f[i-1][j]
- 放入的话 f[i][j] = f[i-1][j-w[i]] + v[i];
所以有以下状态转移方程
$
f[i][j]=
\begin{cases}
0 & if\ min(i,j)=0\\
min \begin{cases}
f[i-1][j] \
f[i-1][j-w[i]] + v[i]
\end{cases}
& otherwise
\end{cases}
$
代码
|
|
复杂度分析
时间复杂度和空间复杂度都是O(mn)
空间优化(状态压缩)
对于状态转移方程,考虑到每个F[i][j]都仅和F[i-1][j]或F[i-1][j-v[i]]有关,那么可以通过利用滚动数组的方式,将F[m+1][c+1]所需要空间压缩至f[2][c+1],从而将空间复杂度降为O(n)。举个例子,我们将f[0][j]状态存在二维表的第0行,接着推出f[1][j]对应的值,并将f[1][j]的状态存放于二维表的第1行。再接着推出f[2][j]的状态时,f[0][j]的状态已经没有保存意义了,因此直接将f[2][j]的状态保存到二维表的第0行,并以此类推,使数组空间得到循环利用。 代码实现:
|
|
在理解了滚动数组优化空间的基础之上,还可以进一步将长度2*(c+1)的二维表进一步压缩成一个长度为c+1的一维数组s,其状态转移方程为f[j]=max(f[j],f[j-w[i]] + v[i])。 这种优化的原理也是非常明显的,先计算F[i-1][j]并存入数组B当中,然后再计算F[i][j]并覆盖数组B中的内容,依次类推直至所有状态求出。由于f[j]可由f[j-w[i]],即F[i][j]可由F[i-1][j-w[i]]推出,因此在覆盖数组时必须采用倒序存储。举个例子,当你计算出f[0]的状态并覆盖掉原来f[0]中的值时,再要求f[1]时,由于f[0]的值已经发生了改变,所以你无法得到正确的f[1]。 代码实现:
|
|
然而,不管是滚动数组还是一维数组,在压缩空间的同时,其带来的缺点也很明显,那就是无法通过回溯的方式将所有的最优解求出。若要通过回溯方式求出最优解,那必须对所有的历史状态都进行保留。而压缩存储空间的同时也压缩了问题的解空间,滚动数组的解空间最多仅能容纳2个物品的解,而一维数组的解空间最多只能容纳1个
总结
1、01背包问题属于NP问题之一,每个物品有选和不选两种策略,若采用暴力搜索算法,其时间复杂度为$O(2^n)$,而采用动态规划的方式,则可以将时间复杂度从$O(2^n)$降到$O(n^2)$,通过自底向上逐层递推可以求得最优解 2、在动态规划的过程中,由于其无后效性,往往能够通过对状态转移方程的分析,使用滚动数组的方式压缩存储空间,当当前状态仅仅与前一状态相关时,甚至可以采用一维数组进行进一步压缩,此时需要特别注意数组下标的遍历次序。