Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
多重背包问题转化为01背包问题时,一定要注意转化方法,WA的同学们!!!假如有一种物品有N个,那么可以转化为2^0,2^1,,,,2^k 因为N有一个对应的二进制表示,所以简单一想 ,肯定可以。 这个时候容易忽略一个东西,k的取值为 N的最高位置,那么无形种把问题扩大了, 因为N很少情况下才全部二进制位是1, 但如果k取值位最高位置-1,又会缩小2^0,2^1,,,,2^k的表示范围。 所以只有一种方法是等价的. 2^0,2^1,,,,2^k-1,N-2^k+1. 用等比数列求和,前面k项的和正好差最后一项 总共加起来等于N。 在整个地方WA了好多次!!! Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator