多重背包的二进制优化

xiaoxiao2021-02-28  11

例如: 当前有一种物品件数为100 那么100=1+2+4+8+16+32+37 所以可以把背包分成以上7个小背包,然后做一次01背包。

原理: 根据二进制的性质,可以知道1 2 4 8 16 32可以构成1~63间任意的一个数, 那么再加上37,就变成38~100间的数, 和原来的1~63一合并,就变成1~100了。

转载请注明原文地址: https://www.6miu.com/read-1100198.html

最新回复(0)