先写个背包问题模板（01，完全，多重，未测试）
摘要: 先写个背包问题模板（01，完全，多重，未测试）
阅读全文
posted @
2009-03-18 23:35 爬 阅读(1838) |
评论 (2) 编辑
pku Cash Machine 多重背包
摘要: http://acm.pku.edu.cn/JudgeOnline/problem?id=1276
将第i种面额分成若干面额的bill，这些bill面额为 系数1，2，4，。。。。2^(k-1),n[i]-2^k+1 分别乘以d[i] ， 并且n[i]-2^k+1>0;
(我也是看别人的，找个数试一下就知道了，用这些面额系数就可以，就可以组成<=n[i]的所有可能)
O(V* S log n[i])
f[v]表示容量v所能得到的总数
简化方程: f[v]=max{f[v],f[v-c]+c}
f[]初始都为0
阅读全文
posted @
2009-03-18 22:42 爬 阅读(1362) |
评论 (2) 编辑