WangYXHaHa

题目链接

Emmmm...一道看似是搜索的题，但是如果直接爆搜的话会直接爆掉的：经计算，爆搜最坏需要搜索1073741823次

所以正解是dp，但这个题让求的不是最大价值（物品连价值都没有），而是最小的剩余空间，于是乎，我们要在标准的动态转移方程上魔改。

首先定义 $F\lbrack i,v\rbrack$ 的含义是当前 $i$ 个物品放到大小为 $v$ 的空间时的最大使用大小，$C_{i}$ 表示第 $i$ 个物品的大小，然后没有 $W_{i}$ ，因为我们要求最大使用大小，$C_{i}$ 和 $W_{i}$ 合二为一了。

那么魔改后的动态转移方程就是这样：

$F\left\lbrack i,\ v \right\rbrack = {\max(}{F\left\lbrack i - 1,v \right\rbrack,F\left\lbrack i - 1,v - C_{i} \right\rbrack + C_{i}})$

最后输出时输出空间大小减去最大使用大小就行了

于是乎最终代码就是这样：

#include <iostream>
using namespace std;

int dp[30+5][20000+10],c[30+5];

int main(){
    int m,n;
    cin >> m >> n;
    for (int i=1;i<=n;i++){
        cin >> c[i];
    }
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++){
            if (j-c[i]>=0) dp[i][j]=max(dp[i-1][j],dp[i-1][j-c[i]]+c[i]);
            else dp[i][j]=dp[i-1][j];
        }
    }
    cout << m-dp[n][m] << endl;
    return 0;
}