2009年3月18日
摘要: 先寫個(gè)背包問題模板（01，完全，多重，未測試）
閱讀全文
posted @
2009-03-18 23:35 爬 閱讀(1861) |
評論 (2) |
編輯 收藏
摘要: http://acm.pku.edu.cn/JudgeOnline/problem?id=1276
將第i種面額分成若干面額的bill，這些bill面額為 系數(shù)1，2，4，。。。。2^(k-1),n[i]-2^k+1 分別乘以d[i] ， 并且n[i]-2^k+1>0;
(我也是看別人的，找個(gè)數(shù)試一下就知道了，用這些面額系數(shù)就可以，就可以組成<=n[i]的所有可能)
O(V* S log n[i])
f[v]表示容量v所能得到的總數(shù)
簡化方程: f[v]=max{f[v],f[v-c]+c}
f[]初始都為0
閱讀全文
posted @
2009-03-18 22:42 爬 閱讀(1428) |
評論 (2) |
編輯 收藏posted @
2009-03-18 19:53 爬 閱讀(1525) |
評論 (0) |
編輯 收藏