看過題后，你可能會發(fā)現(xiàn)這是很典型的0-1背包問題，即要么選擇這件要么不選。

0-1背包問題最經典的解法就是動態(tài)規(guī)劃了。當然這道題的數(shù)據(jù)范圍較小，也可以用暴搜（暴力搜索）來做，即枚舉所有情況。我們用遞歸來實現(xiàn)一下。

對于每一件物品就模擬兩種情況選或者不選，千萬不要漏掉哪一種情況，最后求取最大值就好了。（由于我們當時模擬賽，所以寫了文件讀取數(shù)據(jù)，請見諒。）

好了，暴搜的解法就介紹到這里，接下來，要介紹經典解法——動態(tài)規(guī)劃。

動態(tài)規(guī)劃最重要的就是建立遞推式，根據(jù)上面講解我們已經明確了對于每個物品依次檢查選或不選，用dp[i][j]表示前 i 個物品在 j 金額下的最優(yōu)解（結果最大）。

如果j放不下第i個物品的話，那么就只能從編號為[1,i-1]的物品中選擇了，也就是dp[i-1][j]的值。所以，

dp[i][j] = dp[i-1][j]; （其中，j < v[i]）

那么j可以放的下這個物品的時候應該怎么辦呢？很明顯，我們有兩種選擇，選或不選，之后我們取較大的值。

選     dp[i-1][j-v[i]]+v[i]*p[i];
不選 dp[i-1][j];

所以我們得到遞推式

dp[i][j] = max(dp[i-1][j], dp[i-1][j-v[i]]+v[i]*p[i]);（其中，j>=v[i]）

把兩種情況整理一下，

怎么樣？思路明確多了吧！

根據(jù)遞推式來寫代碼就好了。最后附上AC代碼。