题意： 现在有 \(2n+1\) 个物品（\(n\le 300\)），体积分别为 \(-n,-n+1,\dots,-1,0,1,\dots,n\)，第 \(i\) 个物品有 \(a_i\) 个，求选出恰好 \(S\) 的总体积最多能选几个物品 。
第一步：缩小值域 。不妨设 \(\sum a_i>=S\)，否则将所有数取反 。
【完全背包问题 —— 贪心优化 DP 范围】这时先选完所有的负数，然后不断选正数直至和恰好不超过 S，则此时的和应该属于 \([S-n,S]\)，值域范围被缩小了 。
第二步：缩小状态容易证明，从当前状态直至目标状态，必然存在一个操作序列，使得在任意时刻当前的和属于 \([S-n,S+n]\) 。
第三步：缩小物品数又可以发现，如果存在两个时刻当前时刻的和相同，则这两个时刻之中的操作都是无用的，并且可以证明这一番无用操作一定会减小你所选出的物品数 。于是你最多进行 \(2n+1\) 次改变 。
每次改变至多变化 \(O(n)\)，因此 dp 值域 \(O(n^2)\)，时间复杂度即为 \(O(n^3)\) 。
经验总结扩展阅读
- 项目案例使用有效 解决ffmpeg的播放摄像头的延时优化问题
- C++算法之旅、02 从木棒切割问题领悟二分法精髓
- 教你如何解决T+0的问题
- 哪些星座女在恋爱中对另一半完全依赖
- 注意哪些饮食问题才能保护肾脏
- 大脑多少岁才发育完全
- 6细节帮你发现孩子的视力问题
- 爱上就不考虑亏本不亏本问题的星座
- 累加和为 K 的子数组问题
- 基于PL022 SPI 控制器 海思3516系列芯片SPI速率慢问题深入分析与优化