1. 首頁 > 生活百科 > >

完全背包問題 —— 貪心優化 DP 范圍

生活百科

題意： 現在有 \(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)\) 。
【完全背包問題 —— 貪心優化 DP 范圍】

    推薦閱讀