【NOIP2006普及组】开心的金明

看过题后，你可能会发现这是很典型的0-1背包问题，即要么选择这件要么不选。

0-1背包问题最经典的解法就是动态规划了。当然这道题的数据范围较小，也可以用暴搜（暴力搜索）来做，即枚举所有情况。我们用递归来实现一下。

对于每一件物品就模拟两种情况选或者不选，千万不要漏掉哪一种情况，最后求取最大值就好了。（由于我们当时模拟赛，所以写了文件读取数据，请见谅。）

好了，暴搜的解法就介绍到这里，接下来，要介绍经典解法——动态规划。

动态规划最重要的就是建立递推式，根据上面讲解我们已经明确了对于每个物品依次检查选或不选，用dp[i][j]表示前 i 个物品在 j 金额下的最优解（结果最大）。

如果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]）

把两种情况整理一下，

怎么样？思路明确多了吧！

根据递推式来写代码就好了。最后附上AC代码。