问题
完全背包问题:给定一个容量为v的背包和n种物品,每种物品有无限个且有体积Ci和价值Wi.问最多能向背包中装多少价值的物品?
naive approch
状态表示:F(i,j)仍表示对于前i种物品,背包容量为j时最多价值为多少? 初始情况:F(0,j)=0 状态转移:f(i,j)=max{f(i-1,j-kCi)+kWi} (0<=k<=j/Ci) 复杂度O(V∑V/Ci)
优化
优化1:对于Ci<=Cj,Wi>=Wj的情况,扔掉j 需要O(N^2)进行优化 优化2:基数排序,扔掉Ci>V的i,对0到V每个容量,选择Wi最大的物品. 需要O(V+N)
转化
将完全背包转化为01背包. 第一种转化,每种物品对应为V/Ci个物品 第二种转化,将第i种物品拆分成Ci*2^k,Wi*2^k的若干件物品,满足Ci*2^k<=V即可 每种物品对应log(V/Ci)个物品,优化很大.
O(VN)算法
for(
int i=
1;i<=n;i++)
for(
int j=volume[i];j<=v;j++)
dp[j]=max(dp[j],dp[j-volume[i]]+value[i]);
这个算法与01背包空间优化后的算法,只有j的遍历顺序相反. 因为01背包倒序遍历就是为了避免一件物品被计算多次. 两层循环可以交换顺序,某些情况下带来常数优化???
习题集
见之后的博客
