【正经题解】装箱问题

这道题看似是搜索，但是可以用背包做。
题目要求求出最小的剩余空间，也就是要求出最大的可装重量
这样，我们可以将一个物体的重量当作它的价值，进而将题目转变为一个基本的 $01$ 背包问题：
有一个箱子容量为 $V$ （正整数， $0$ ＜＝ $V$ ＜＝ $20000$ ），同时有 $n$ 个物品（ $0$ ＜ $n$ ＜＝ $30$ ），每个物品有一 个体积（正整数）和一个价值（等于体积）。
要求 $n$ 个物品中，任取若干个装入箱内，使总价值最大。
对于每一个物体，都有两种状态：装 与不装
那么，对于任意重量 $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$ 后，箱子能装的最大重量

#include<cstdio>
using namespace std;
int m,n;              //  m即箱子容量V
int f[20010];
int w[40];
int main(){
    int i,j;
    scanf("%d%d",&m,&n);
    for(i=1;i<=n;i++){
        scanf("%d",&w[i]);
    }
    for(i=1;i<=n;i++){
        for(j=m;j>=w[i];j--){                         //   注意：这里必须是从m到w[i]，否则一个物体会被多次装入箱子，见例1
            if(f[j]<f[j-w[i]]+w[i]){
                f[j]=f[j-w[i]]+w[i];
            }
        }
    }
    printf("%d\n",m-f[m]);
}