看过题后,你可能会发现这是很典型的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代码。
联系客服