多重背包中多次背包 O(VN) 算法2 (线性动规) 带参考程序_sy2006
其实解决多次背包问题还可以用线性动规的方法（类似NOIP2009普及组道路游戏的算法）
设背包容量t，物品件数n，每件物品体积m[i]，价值s[i]，可用次数c[i](0表示无限制)
用 b[j,i] 记录到容量为j的情况下物品i使用次数，f[j] 记录容量为j的情况的最优解。
动规的时候，将j从1到t循环一次，分别求解f[j]
对于每个f[j],可以从f[j-m[i]] (i=1..n)得来
转移方程为f[j]=max(f[j-m[i]]+s[i]) (i=1..n, 且满足 j>=m[i] , b[j-m[i],i]<c[i])
且 b[j]=b[j-m[i]]; b[j,i]:=b[j,i]+1;
Read full article from 多重背包中多次背包 O(VN) 算法2 (线性动规) 带参考程序_sy2006
No comments:
Post a Comment