这题一眼就能看出是01背包问题,但是跟模板不太一样:每个物品只有重量,没有价值,而且求的是背包剩余的最小容量。但你仔细思考也会发现这个问题与01背包模板题是可以转化的。既然每个物品没有价值,那么就把它们的价值定义为它们的重量,求剩余最小容量的问题就变成了求剩余最少价值。然后你会发现,用总价值减去装了的价值,就是问题的答案。总价值是什么?是背包的容量V,也就是背包装的价值上限。
所以,我们只要把这道题当作01背包模板题做就行了。
注意:把所有代表价值的数组全部换成代表重量的数组,最后的答案应该是V-dp[n][V],也就是背包容量减去最大能装的重量就是剩余最小重量。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
AC代码(如果你看懂了,你应该不会抄)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------