題目1 : 完全背包
時間限制: 20000ms 單點時限: 1000ms 記憶體限制: 256MB
-
5 1000 144 990 487 436 210 673 567 58 1056 897 樣例輸出 -
5940
描述
且說之前的故事裡，小Hi和小Ho費勁心思終于拿到了茫茫多的獎券！而現在，終于到了小Ho領取獎勵的時刻了！
等等，這段故事為何似曾相識？這就要從平行宇宙理論說起了………總而言之，在另一個宇宙中，小Ho面臨的問題發生了細微的變化！
小Ho現在手上有M張獎券，而獎品區有N種獎品，分别标号為1到N，其中第i種獎品需要need(i)張獎券進行兌換，并且可以兌換無數次，為了使得辛苦得到的獎券不白白浪費，小Ho給每件獎品都評了分，其中第i件獎品的評分值為value(i),表示他對這件獎品的喜好值。現在他想知道，憑借他手上的這些獎券，可以換到哪些獎品，使得這些獎品的喜好值之和能夠最大。
令人欣慰的是，在這個平行世界裡小Ho已經學習了一般的01背包問題，是以他并沒有思考太久，便提出了自己的想法。
“我們的首要目标仍然是将問題抽象化！在我看來，這個問題其實和01背包問題很像，我們在解決01背包問題的時候是按照獎品的标号從1到N依次決定每件獎品是否選取，那麼對于每種獎品有無數件的這個問題，我可以按照獎品的标号從1到N依次決定每種獎品選取的件數！”
小Hi點了點頭表示贊同。
小Ho于是繼續說道：“那麼按照01背包的想法，我可以使用best(i, x)表示已經決定了前i件物品每件物品選擇多少件，目前已經選取的物品的所需獎券數總和不超過x時，能夠擷取的最高的喜好值的和，那麼最終的答案便是best(N, M)。”
小Hi道：”的确可以這樣，那麼你準備如何轉移呢？”
小Ho道：“仍然是根據01背包的做法，對于一個問題best(i, x)，考慮最後一步——即第i件物品選擇多少件，不妨就假設選擇k件吧，那麼k的取值範圍肯定是在0~(x / need(i))這個範圍内。這個時候我們可以知道best(i - 1, x - need(i) * k) + value(i) * k将會是一種可能的方案。”
小Hi撓了撓頭，問道：”你所說的‘可能的方案’是什麼意思？”
小Ho笑道：“就是說best(i, x)的求解滿足這個公式~”
說罷，拿過紙筆，列出了一個式子。
小Hi接過紙來，看完說道：“的确沒錯，總共就是這些可能~那你是否求解這個問題也是用與01背包類似的方法進行求解呢？”
“是的，我會使用這樣的方法來做！”小Ho刷刷刷又在紙上寫下來幾行僞代碼。
“應該沒有問題，時間複雜度也很不錯了~~但是我看着總有點難受！”小Hi點了點頭又搖頭。
“怎麼說？”
小Hi嘻嘻笑了兩聲，說道：“我們不妨換一種問題定義的方式：用best(i, x)表示已經決定了前i件物品每件物品選擇多少件，目前已經選取的物品的所需獎券數總和不超過x時，能夠擷取的最高的喜好值的和！”
小Ho仔仔細細回憶了下，确認小Hi所說和自己先前并無差別，怒道：“你這和我的定義方法有什麼差別呀？”
小Hi道：“别急别急，這部分的确沒有差別，有差別的在後頭~”
小Ho撇了撇嘴：“那你就說呗~”
小Hi繼續道：“我們還是考慮最後一步——要不要再選一件第i種獎品！”
小Ho有點不能了解，道：“什麼叫再選一件？”
“你想想，在你的狀态轉移方程（即問題求解公式）中是否滿足這樣兩個公式？”小Hi問道。
小Ho低頭想了想，點了點頭表示贊同。
小Hi于是繼續問道：“那你有沒有意識到這樣一個等式？”
“似乎……是的！”小Ho驚道：“這麼說，其實best(i, x)的大部分計算都在best(i, x - need(i))中已經計算過了！”
小Hi問出了最後一個問題：“是以你的公式是不是就可以變成這樣子呢？”
“是的！是以……代碼就可以這麼寫了~是麼！”
輸入
每個測試點（輸入檔案）有且僅有一組測試資料。
每組測試資料的第一行為兩個正整數N和M,表示獎品的種數，以及小Ho手中的獎券數。
接下來的n行描述每一行描述一種獎品，其中第i行為兩個整數need(i)和value(i)，意義如前文所述。
測試資料保證
對于100%的資料，N的值不超過500，M的值不超過10^5
對于100%的資料，need(i)不超過2*10^5, value(i)不超過10^3
輸出
對于每組測試資料，輸出一個整數Ans，表示小Ho可以獲得的總喜好值。
樣例輸入
#define L 100050
#define N 505
int main(){
ll dp[L],w[N],v[N];
int n,m,i,j;
scanf("%d%d",&n,&m);
for(i=0;i<n;i++)
scanf("%lld%lld",&w[i],&v[i]);
for(i=0;i<n;i++)
for(j=w[i];j<=m;j++)
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
printf("%lld\n",dp[m]);
return 0;
}