本文共 916 字,大约阅读时间需要 3 分钟。
01背包问题的具体描述自行百度:
有N件物品和一个容量为V的背包。第i件物品的重量是c[i],价值是w[i]。
求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量,且价值总和最大。(01背包中这些物品每种都只有1个,每个物品只能装一次)
基本问题
用子问题定义状态:即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。
则其状态转移方程便是:f[i][v]=max{ f[i-1][v], f[i-1][v-c[i]]+w[i] }。可以压缩空间,f[v]=max{f[v],f[v-c[i]]+w[i]}
为什么逆序
逆序的关键就在于这个状态转移方程
f[i][v]只与f[i-1][v]和f[i-1][v-C[i]]有关,即只和i-1时刻状态有关,所以我们只需要用一维数组f[]来保存i-1时的状态f[]。
假设i-1时刻的f[]为{a0,a1,a2,…,av},那么i时刻的f[]中第v个应该为max(av,av-C[i]+W[i])即max(f[v],f[v-C[i]]+W[i]),
这就需要我们遍历V时逆序遍历,这样才能保证求i时刻f[v]时f[v-C[i]]是i-1时刻的值。如果正序遍历则当求f[v]时
其前面的f[0],f[1],…,f[v-1]都已经改变过,里面存的都不是i-1时刻的值,这样求f[v]时利用f[v-C[i]]必定是错的值。最后f[V]即为最大价值。
数组遍历有时候必须逆序大多是这个原因。
转载地址:http://hlcgi.baihongyu.com/