背景：
原题链接
背包动态规划模板题，但又要点优化。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
思路：
> 多重背包模板题，但由于数据范围1≤n,m,wi,vi,cnti≤10001\leq n,m,w_i,v_i,cnt_i\leq10001≤n,m,wi ,vi ,cnti ≤1000，如果将每个物品都拆分成01背包，那么最多有n×cntn \times cntn×cnt个物品，最多10610^6106，再按01背包最坏时间复杂度为O(n×cnt×m)O(n \times cnt \times m)O(n×cnt×m)，1s内根本运行不完，所以要用倍增法优化。（详细讲解——OI Wiki）
> 将数量每个cntcntcnt拆分为各不相同的222的整数次幂，要是有剩下的就用剩下的。如数量131313拆分为20+21+22+62^0+2^1+2^2+620+21+22+6，252525拆分为20+21+22+23+102^0+2^1+2^2+2^3+1020+21+22+23+10，再将这些数乘以相应的重量和价值，成为01背包的一个物品，这样时间复杂度就能降为O(m×∑i=1nlogcnti)O(m \times \sum^{n}_{i=1}{\log cnt_i})O(m×∑i=1n logcnti )，1s内完全可以运行完。最后写一遍01背包模板即可。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
代码：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
结语：
希望对大家学习OI有帮助！
