Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

多重背包问题转化为01背包问题时,一定要注意转化方法,WA的同学们!!!

Posted by tangguojun at 2016-10-14 11:24:56 on Problem 1276
   假如有一种物品有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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator