背包九讲——全篇详细理解与代码实现-CSDN博客一、标准数学名称1. 正式定理二进制表示定理Binary Representation Theorem核心结论任意正整数都可以唯一表示为若干互不相同的 2 的幂之和\(n a_02^0a_12^1a_22^2\dotsa_k2^k,\quad a_i\in\{0,1\}\) 也就是我们日常的二进制进制原理。2. 算法领域俗称二进制拆分原理 / 倍增原理OI / 算法圈讲多重背包二进制优化时不会叫冗长的 “二进制表示定理”一般直接叫二进制拆分原理底层依托上面的二进制表示定理。二、和多重背包拆分的对应解释定理保证\(0 \sim p\) 之间任意整数都能用 \(1,2,4,\dots,2^k\) 若干个数相加得到。 举例最多取 13 件物品按 2 的幂拆分\(1,2,4\)剩余余数 \(13-(124)6\)\(0\sim13\) 任何数字都能由其中若干组合\(514\)、\(7124\)、\(131246\)把每组等价打包成一件新物品直接转 01 背包复杂度从 \(O(V\sum p)\) 降到 \(O(V\sum \log p)\)三、补充数论底层支撑除法算法二进制表示定理的严格证明依托带余除法除法算法 Division Algorithm 对任意整数 \(a,b(b0)\)存在唯一 \(q,r\) 满足 \(a bq,\ 0\le rb\)反复对 2 取余就能得到二进制每一位 0/1证明该表示唯一存在。总结严谨数学定理二进制表示定理算法竞赛叫法二进制拆分原理倍增思想底层证明工具带余除法除法算法
尧图网络