背包九讲完全背包 转化为01背包问题求解 数学原理

背包九讲——全篇详细理解与代码实现-CSDN博客

一、标准数学名称

1. 正式定理：二进制表示定理（Binary Representation Theorem）

核心结论：任意正整数都可以唯一表示为若干互不相同的 2 的幂之和\(n = a_02^0+a_12^1+a_22^2+\dots+a_k2^k,\quad a_i\in\{0,1\}\) 也就是我们日常的二进制进制原理。

2. 算法领域俗称：二进制拆分原理 / 倍增原理

OI / 算法圈讲多重背包二进制优化时，不会叫冗长的 “二进制表示定理”，一般直接叫二进制拆分原理，底层依托上面的二进制表示定理。

二、和多重背包拆分的对应解释

定理保证：\(0 \sim p\) 之间任意整数，都能用 \(1,2,4,\dots,2^k\) 若干个数相加得到。 举例：最多取 13 件物品

1. 按 2 的幂拆分：\(1,2,4\)，剩余余数 \(13-(1+2+4)=6\)
2. \(0\sim13\) 任何数字都能由其中若干组合：
   • \(5=1+4\)、\(7=1+2+4\)、\(13=1+2+4+6\)
3. 把每组等价打包成一件新物品，直接转 01 背包，复杂度从 \(O(V\sum p)\) 降到 \(O(V\sum \log p)\)

三、补充：数论底层支撑（除法算法）

二进制表示定理的严格证明依托带余除法（除法算法 Division Algorithm）： 对任意整数 \(a,b(b>0)\)，存在唯一 \(q,r\) 满足 \(a = bq,\ 0\le r<b\)；反复对 2 取余就能得到二进制每一位 0/1，证明该表示唯一存在。

总结

• 严谨数学定理：二进制表示定理
• 算法竞赛叫法：二进制拆分原理（倍增思想）
• 底层证明工具：带余除法（除法算法）