题解 | #[NOIP2001]装箱问题#

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    int v;
    cin >> v;
    cin >> n;//dp[v]的意思为：容量为v时，能装的最大体积。
    vector<int>dp(v+1,0);//本质还是01背包问题，剩余空间最小就是价值最大的意思。01背包算出能装最多的空间，
    vector<int>volum(n);//再用v-dp[v]就得剩下的最小空间。
    for(int i = 0;i < n;i++)
        cin >> volum[i];
    for(int i = 0;i < n ;i++)
    {
        for(int j = v;j >= volum[i];j--)
        {
            dp[j] = max(dp[j],dp[j-volum[i]] + volum[i]);
        }
    }
    cout << v-dp[v] <<endl;
    return 0;
}