一个资深小白的理解~~
引用最常见的问题:有N种物品和一个容量为V的背包,每种物品都有无限件可用。第i种物品的费用是c[i],价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。与01背包不同的是每种物品可以取多次,
01背包的状态方程是f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+v[i];
完全背包的状态方程是f[i][j]=max{f[i-1][j-k*w[i]]+k*v[i]|0<=k*c[i]<=j}可见,当k=0和1时就是01背包的状态方程。
对于这个状态方程需要关于i,j,k的三重循环。
关于优化问题:化简状态方程f[i][j]=max{f[i-1][j-k*w[i]]+k*v[i]|0<=k*w[i]<=j}
=max(f[i-1][j],max{f[i-1][j-k*w[i]]+k*v[i]|k>=1})=max(f[i-1][j],f[i][j-w[i]]+v[i])
若两件物品满足C[i] ≤C[j]&&W[i] ≥W[j]时将第j种物品直接筛选掉。因为第i种物品比第j种物品物美价廉,用i替换j得到至少不会更差的方案。
这个筛选过程如下:先找出体积大于背包的物品直接筛掉一部分(也可能一种都筛不掉)复杂度O(N)。利用计数排序思想对剩下的物品体积进行
排序,同时筛选出同体积且价值最大的物品留下,其余的都筛掉(这也可能一件都筛不掉)复杂度O(V)。
整个过程时间复杂度为O(N+V)时间复杂度优化为O(NV)
设F[i][j]表示出在前i种物品中选取若干件物品放入容量为j的背包所得的最大价值。那么对于第i种物品的出现,我们对第i种物品放不放入背包
进行决策。如果不放那么F[i][j]=F[i-1][j];如果确定放,背包中应该出现至少一件第i种物品,所以F[i][j]种至少应该出现一件第i种物品,
即F[i][j]=F[i][j-C[i]]+W[i]。为什么会是F[i][j-C[i]]+W[i]?因为我们前面已经最大限度的放了第i件物品,如果能放就放这最后的一件,
(或者理解为前面已经往背包中放入了第i件物品,我们每一次只增加一件的往背包里放,而且只能增加一件,多了放不下)
状态方程为:
关于空间优化 稍后再补