hiho一下 第七周 Hihocoder #1043 : 完全背包
題目1 : 完全背包
時(shí)間限制:20000ms 單點(diǎn)時(shí)限:1000ms 內(nèi)存限制:256MB描述
且說之前的故事里，小Hi和小Ho費(fèi)勁心思終于拿到了茫茫多的獎券！而現(xiàn)在，終于到了小Ho領(lǐng)取獎勵的時(shí)刻了！
等等，這段故事為何似曾相識？這就要從平行宇宙理論說起了………總而言之，在另一個宇宙中，小Ho面臨的問題發(fā)生了細(xì)微的變化！
小Ho現(xiàn)在手上有M張獎券，而獎品區(qū)有N種獎品，分別標(biāo)號為1到N，其中第i種獎品需要need(i)張獎券進(jìn)行兌換，并且可以兌換無數(shù)次，為了使得辛苦得到的獎券不白白浪費(fèi)，小Ho給每件獎品都評了分，其中第i件獎品的評分值為value(i),表示他對這件獎品的喜好值。現(xiàn)在他想知道，憑借他手上的這些獎券，可以換到哪些獎品，使得這些獎品的喜好值之和能夠最大。
令人欣慰的是，在這個平行世界里小Ho已經(jīng)學(xué)習(xí)了一般的01背包問題，所以他并沒有思考太久，便提出了自己的想法。
“我們的首要目標(biāo)仍然是將問題抽象化！在我看來，這個問題其實(shí)和01背包問題很像，我們在解決01背包問題的時(shí)候是按照獎品的標(biāo)號從1到N依次決定每件獎品是否選取，那么對于每種獎品有無數(shù)件的這個問題，我可以按照獎品的標(biāo)號從1到N依次決定每種獎品選取的件數(shù)！”
小Hi點(diǎn)了點(diǎn)頭表示贊同。
小Ho于是繼續(xù)說道：“那么按照01背包的想法，我可以使用best(i, x)表示已經(jīng)決定了前i件物品每件物品選擇多少件，當(dāng)前已經(jīng)選取的物品的所需獎券數(shù)總和不超過x時(shí)，能夠獲取的最高的喜好值的和，那么最終的答案便是best(N, M)。”
小Hi道：”的確可以這樣，那么你準(zhǔn)備如何轉(zhuǎn)移呢？”
小Ho道：“仍然是根據(jù)01背包的做法，對于一個問題best(i, x)，考慮最后一步——即第i件物品選擇多少件，不妨就假設(shè)選擇k件吧，那么k的取值范圍肯定是在0~(x / need(i))這個范圍內(nèi)。這個時(shí)候我們可以知道best(i - 1, x - need(i) * k) + value(i) * k將會是一種可能的方案。”
小Hi撓了撓頭，問道：”你所說的‘可能的方案’是什么意思？”
小Ho笑道：“就是說best(i, x)的求解滿足這個公式~”
說罷，拿過紙筆，列出了一個式子。
小Hi接過紙來，看完說道：“的確沒錯，總共就是這些可能~那你是否求解這個問題也是用與01背包類似的方法進(jìn)行求解呢？”
“是的，我會使用這樣的方法來做！”小Ho刷刷刷又在紙上寫下來幾行偽代碼。
“應(yīng)該沒有問題，時(shí)間復(fù)雜度也很不錯了~~但是我看著總有點(diǎn)難受！”小Hi點(diǎn)了點(diǎn)頭又搖頭。
“怎么說？”
小Hi嘻嘻笑了兩聲，說道：“我們不妨換一種問題定義的方式：用best(i, x)表示已經(jīng)決定了前i件物品每件物品選擇多少件，當(dāng)前已經(jīng)選取的物品的所需獎券數(shù)總和不超過x時(shí)，能夠獲取的最高的喜好值的和！”
小Ho仔仔細(xì)細(xì)回憶了下，確認(rèn)小Hi所說和自己先前并無區(qū)別，怒道：“你這和我的定義方法有什么區(qū)別呀？”
小Hi道：“別急別急，這部分的確沒有區(qū)別，有區(qū)別的在后頭~”
小Ho撇了撇嘴：“那你就說唄~”
小Hi繼續(xù)道：“我們還是考慮最后一步——要不要再選一件第i種獎品！”
小Ho有點(diǎn)不能理解，道：“什么叫再選一件？”
“你想想，在你的狀態(tài)轉(zhuǎn)移方程（即問題求解公式）中是否滿足這樣兩個公式？”小Hi問道。
小Ho低頭想了想，點(diǎn)了點(diǎn)頭表示贊同。
小Hi于是繼續(xù)問道：“那你有沒有意識到這樣一個等式？”
“似乎……是的！”小Ho驚道：“這么說，其實(shí)best(i, x)的大部分計(jì)算都在best(i, x - need(i))中已經(jīng)計(jì)算過了！”
小Hi問出了最后一個問題：“所以你的公式是不是就可以變成這樣子呢？”
“是的！所以……代碼就可以這么寫了~是么！”
“是的嗯~”
輸入
每個測試點(diǎn)（輸入文件）有且僅有一組測試數(shù)據(jù)。
每組測試數(shù)據(jù)的第一行為兩個正整數(shù)N和M,表示獎品的種數(shù)，以及小Ho手中的獎券數(shù)。
接下來的n行描述每一行描述一種獎品，其中第i行為兩個整數(shù)need(i)和value(i)，意義如前文所述。
測試數(shù)據(jù)保證
對于100%的數(shù)據(jù)，N的值不超過500，M的值不超過10^5
對于100%的數(shù)據(jù)，need(i)不超過2*10^5, value(i)不超過10^3
輸出
對于每組測試數(shù)據(jù)，輸出一個整數(shù)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; }
總結(jié)
以上是生活随笔為你收集整理的hiho一下 第七周 Hihocoder #1043 : 完全背包的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： hiho一下 第六周 Hihocoder
- 下一篇： Ansj配置指南！