完全背包问题 —— 贪心优化 DP 范围

乎语百科 120 0

题意: 现在有 \(2n+1\) 个物品(\(n\le 300\)),体积分别为 \(-n,-n+1,\dots,-1,0,1,\dots,n\),第 \(i\) 个物品有 \(a_i\) 个,求选出恰好 \(S\) 的总体积最多能选几个物品。

第一步:缩小值域。

不妨设 \(\sum a_i>=S\),否则将所有数取反。

这时先选完所有的负数,然后不断选正数直至和恰好不超过 S,则此时的和应该属于 \([S-n,S]\),值域范围被缩小了。

第二步:缩小状态

容易证明,从当前状态直至目标状态,必然存在一个操作序列,使得在任意时刻当前的和属于 \([S-n,S+n]\)。

第三步:缩小物品数

又可以发现,如果存在两个时刻当前时刻的和相同,则这两个时刻之中的操作都是无用的,并且可以证明这一番无用操作一定会减小你所选出的物品数。于是你最多进行 \(2n+1\) 次改变。

每次改变至多变化 \(O(n)\),因此 dp 值域 \(O(n^2)\),时间复杂度即为 \(O(n^3)\)。

标签:

留言评论

  • 这篇文章还没有收到评论,赶紧来抢沙发吧~