解法:
01背包 dp
为什么可以用01背包来解?
当我开始思考这道题的时候,首先排除的01背包,一方面感觉V太大,另一方面是存在一个误解:最后得出的最大值有可能超过箱子的容量。
实则不然,当物品的价值等于物品的大小时,计算dp[i][j]的过程中,j(容量)一直限制dp[i][j]的大小,dp[i][j]最大也只能等于j。
因此可以放心用01背包来解。
01背包 dp
当我开始思考这道题的时候,首先排除的01背包,一方面感觉V太大,另一方面是存在一个误解:最后得出的最大值有可能超过箱子的容量。
实则不然,当物品的价值等于物品的大小时,计算dp[i][j]的过程中,j(容量)一直限制dp[i][j]的大小,dp[i][j]最大也只能等于j。
因此可以放心用01背包来解。