P1049 [NOIP2001 普及组] 装箱问题

这题看上去像搜索，但实际上是一题典型的01背包问题。

题目思路

题目要求求出最小的剩余空间，也就是要求出最大的可装重量。

这样，我们可以将一个物体的重量当作它的价值，进而将题目转变为一个基本的01背包问题。

对于每一个物体，都有两种状态：装与不装。

那么，对于任意重量m的最大价值f(m)=max(f(m-w[i])+w[i],f(m)) (w为重量(即价值))。

其中，f(m-w[i])指在装了物品i后，箱子的剩余容量能装的最大重量。

f(m-w[i])+w[i]指在在装了物品i后，箱子能装的最大重量。

OK，上代码