01 背包的二进制优化

也是在刷题的时候发现的,比如 hiho week 195。一眼看过去就是一个 0-1 背包问题,然后直接 DP 上了,当时觉得应该问题不大,结果最后只有 50%,一看数据,100% 的数据为 1E5 量,简单的 DP 的话复杂度为 O(MN),这样复杂度估计是 1E10,这样肯定会 TLE。 然后一看,他的单个商品的全权值很低,都在 [1, 10]…